Are there fast(er) ways to compute inverses of Hermitian matrices?

asked 2020-05-30 07:51:15 +0200

sum8tion gravatar image

updated 2020-06-01 17:46:12 +0200

I'm dealing with some Hermitian matrices valued in symbolic expressions. I need to be able to compute inverses of these matrices, but they seem to get big pretty fast. That is it would nice to be able to do this in a reasonable amount of time with 10x10 matrices at least, and hopefully larger than that.
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes.

Are there ways to exploit the fact that these matrices are Hermitian to compute the inverses faster, and/or are there better ways to compute inverses of symbolic matrices than the standard .inverse()??

EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below.

First we have two variables which for which I want to run the larger program for various choices thereof.

p = 1, q= 5

X = {(i): var("X_{}".format(i), latex_name="X_{}") for i in range(2*p*q)}

e = {(i,j,k): var("e_{}{}{}".format(i,j,k), latex_name="e_{{{}{}{}}}".format(i,j,k)) for i in range(2) for j in range(q) for k in range((p+q))}

The following creates a list L such that L[i] is the collection of lists of length i whose elements are integers between 0 and q-1 in strictly increasing order. This is used throughout the larger program.

L = [[[]]]

LL = []
for i in range(q):
    LL.append([i])
L.append(LL)

if q>=2:
    for k in range(2,q+1):
        LLL = []
        for i in range(binomial(q, k-1)):
            for j in range(q):
                if L[k-1][i][len(L[k-1][i])-1]<j:
                    mm = []
                    for t in L[k-1][i]:
                        mm.append(t)
                    mm.append(j)
                    LLL.append(mm)
        L.append(LLL)

Here, a matrix is defined which we be used to construct the matrices I'm interested in.

HE = matrix(SR, q, q)

for i in range(q):
    for j in range(q):
        prod = 0
        for k in range(p):
            prod -= (e[(0, i, k)]*e[(1, j, k)])
        for l in range(p+q):
            if l>=p:
                prod += (e[(0, i, l)]*e[(0, j, l)])
        HE[i,j] = prod

h = {(i): var("h_{}".format(i)) for i in range(q+1)}

for i in range(q+1):
    h[i] = matrix(SR, binomial(q, i), binomial(q, i))

h[0][0,0] = 1

for i in range(1, q+1):
    for z in L[i]:
        for w in L[i]:
            h[i][L[i].index(z), L[i].index(w)] = HE[z, w].det()

Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices.

hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}

for i in range(q+1):
    hinv[i] = h[i].inverse()
edit retag flag offensive close merge delete

Comments

1

"How symbolic" are they? What do the entries look like? Polynomials? Rational functions? Worse? You might benefit from changing the ring. Also, inverting is usually best avoided. Are you sure it's necessary? In any case, an example would help.

rburing gravatar imagerburing ( 2020-05-30 10:58:26 +0200 )edit
1

Please provide an explicit and typical example that we can reproduce so that someone can give a try.

tmonteil gravatar imagetmonteil ( 2020-05-30 13:03:21 +0200 )edit

If everything is polynomial, you should work with polynomial rings and avoid SR at all.

FrédéricC gravatar imageFrédéricC ( 2020-06-01 18:14:22 +0200 )edit
1

How do these matrices become Hermitian?

mwageringel gravatar imagemwageringel ( 2020-06-01 19:31:52 +0200 )edit

@Frederic are computations in polynomial rings that much faster? I was under the impression they worked the same as symbolic rings. I tried rewriting the code using a polynomial ring, but it seemed to make no difference in the run time when q=4, and certainly q=5 still isn't feasible.

sum8tion gravatar imagesum8tion ( 2020-06-03 16:19:49 +0200 )edit