Ask Your Question
0

How to use parallel program to select the longest element in a list?

asked 2022-04-20 11:49:26 +0200

lijr07 gravatar image

updated 2022-04-20 13:55:11 +0200

I need to find the longest element in a list of elements of Weyl group. The way I do it is:

    winner = W.one()
    for u1 in g1:
        for u2 in g2:
            t1=u1*w*u2
            if t1.length()>winner.length():
                winner=t1
    r=winner

Here g1 and g2 are two given subsets of the Weyl group I would like to make the above faster by using parallel computations. Is there some way in Sage or Python to do this? Thank you very much!

Edit: the full codes are:

def find_permutation2(L1, L2):
    perm = Word(L1).standard_permutation() / Word(L2).standard_permutation()
    assert [L2[i-1] for i in perm] == L1
    r=perm.reduced_word()
    return r

def LongestPermWInSBWInverseSA(W,A,B): 
    t1=StablizerOfTuple(A)
    t2=StablizerOfTuple(sorted(B))
    s=W.simple_reflections()
    #print(t1,t2)
    t3=[]
    for i in t1:
        t3.append(s[i])
    t4=[]
    for i in t2:
        t4.append(s[i])
    t5=find_permutation2(B,sorted(B))
    w=W.one()
    for i in t5:
        w=w*s[i]
    #print(t4,w,t3)
    r2=LongestPermInDoubleCosetWeylGroup(W,t4,w,t3)
    r=r2

    return r


def LongestPermInDoubleCosetWeylGroup(W,S1,w,S2): 
    g1=W.subgroup(S1)
    g2=W.subgroup(S2)
    winner = W.one()
    for u1 in g1:
        for u2 in g2:
            t1=u1*w*u2
            if t1.length()>winner.length():
                winner=t1
    r=winner

    return r

def SymmetricGroupActionOnListSi(i,L): #  w=s_i,  L=[a1,a2,...,an]
    r1=[]
    for j in L:
        r1.append(j)

    t1=r1[i-1]
    r1[i-1]=r1[i]
    r1[i]=t1 

    r=r1

    return r

def StablizerOfTuple(A): # A is a list, weakly increasing
    k = len(A)
    r=[]
    for i in [1..k-1]:
        t1=SymmetricGroupActionOnListSi(i,A)
        if t1==A:
            r.append(i)
    return r

A=[1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]
B=[3, 3, 3, 5, 5, 5, 4, 4, 4, 6, 6, 6]
kk=len(A)
#print(kk)
typ='A' 
W=SymmetricGroup(kk)
w=LongestPermWInSBWInverseSA(W,A,B)
w
edit retag flag offensive close merge delete

Comments

At very least you can speed up things by factor of 2 or so if you take multiplication u1*w out of the inner loop.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-04-20 14:10:41 +0200 )edit

2 Answers

Sort by » oldest newest most voted
1

answered 2022-04-20 15:11:58 +0200

Max Alekseyev gravatar image

You can try something like this:

import functools
import multiprocessing

N_CPU = multiprocessing.cpu_count()
print('CPUs:',N_CPU)

def myprod(g1,w,u2):
    return max(t*w*u2 for t in g1, key=lambda t: t.length())

with multiprocessing.Pool(processes=N_CPU) as pool:
    winner = max( pool.imap_unordered(functools.partial(myprod,g1,w), g2), key=lambda t: t.length() )
edit flag offensive delete link more

Comments

@max, thank you very much for your helpful answer!

lijr07 gravatar imagelijr07 ( 2022-04-20 16:54:03 +0200 )edit
1

answered 2022-04-20 12:53:45 +0200

Sébastien gravatar image

The first thing you can try is using max with a key function to compare the elements by their length:

sage: G = WeylGroup(['F',4])
sage: %time w_max = max(G, key=lambda w:w.length())
CPU times: user 3.09 s, sys: 18 µs, total: 3.09 s
Wall time: 3.09 s
sage: w_max.length()
24
sage: w_max
[-1  0  0  0]
[ 0 -1  0  0]
[ 0  0 -1  0]
[ 0  0  0 -1]

Is the above 3s is too slow? If yes, it would be interesting to implement a max function in Sage which would do the computation in parallel, maybe using the @parallel decorator?

edit flag offensive delete link more

Comments

@Sebastien, thank you very much for your help. One problem is that I need to find the longest word in a subset of Weyl group (not the whole Weyl group) which satisfies certain properties. I attached the full codes. In the example in the end of the codes, it takes very long time to compute. So I would like to parallelize it and send it to a computer cluster.

lijr07 gravatar imagelijr07 ( 2022-04-20 13:57:57 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-04-20 11:49:26 +0200

Seen: 36 times

Last updated: Apr 20