ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 03 Jun 2020 16:22:54 +0200Are there fast(er) ways to compute inverses of Hermitian matrices?https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/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()Sat, 30 May 2020 07:51:15 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/Comment by rburing for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51640#post-id-51640"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.Sat, 30 May 2020 10:58:26 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51640#post-id-51640Comment by tmonteil for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51642#post-id-51642Please provide an explicit and typical example that we can reproduce so that someone can give a try.Sat, 30 May 2020 13:03:21 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51642#post-id-51642Comment by FrédéricC for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51680#post-id-51680If everything is polynomial, you should work with polynomial rings and avoid SR at all.Mon, 01 Jun 2020 18:14:22 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51680#post-id-51680Comment by mwageringel for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51682#post-id-51682How do these matrices become Hermitian?Mon, 01 Jun 2020 19:31:52 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51682#post-id-51682Comment by sum8tion for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51721#post-id-51721@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.Wed, 03 Jun 2020 16:19:49 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51721#post-id-51721Comment by sum8tion for <p>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. <br>
I'm currently running a cell where the inverses of 2 10x10 matrices are being computed, and it's taken well over 10 minutes. </p>
<p>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()??</p>
<p>EDIT: I originally avoided an example, because their construction is somewhat convoluted as you'll see below. </p>
<p>First we have two variables which for which I want to run the larger program for various choices thereof. </p>
<pre><code>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))}
</code></pre>
<p>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. </p>
<pre><code>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)
</code></pre>
<p>Here, a matrix is defined which we be used to construct the matrices I'm interested in. </p>
<pre><code>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()
</code></pre>
<p>Finally, we come to the inverse matrices I would like to compute. It is absolutely necessary that I have these inverse matrices. </p>
<pre><code>hinv = {(i): var("hinv_{}".format(i)) for i in range(q+1)}
for i in range(q+1):
hinv[i] = h[i].inverse()
</code></pre>
https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51722#post-id-51722@mwageringel It's a little convoluted, by the symbolic variables I have set up are supposed to represent complex numbers, and part of the indexing reflects conjugation. Under this identification the matrices h[i] can be seen as Hermitian matrices. If you'd really like I can explain the details, but I don't think they're relevant to the question at hand.Wed, 03 Jun 2020 16:22:54 +0200https://ask.sagemath.org/question/51638/are-there-faster-ways-to-compute-inverses-of-hermitian-matrices/?comment=51722#post-id-51722