why eigenvectors very slow

[monde wilson]

why eigenvectors very slow

what is the difference between numpy and sympy when doing matrix calculation

will numpy faster and more accurate?

import csv as csv

from sympy import *

data = []

open1 = []

high1 = []

low1 = []

close1 = []

date1 = []

list_t1 = []

path = r'C:\Users\wilson\Downloads\Downloads\execution.csv'

with open(path, 'rb') as csvfile:

readdata=csv.reader(csvfile)

count = 0

for row in readdata:

date1.append(row[0])

open1.append(row[1])

high1.append(row[2])

low1.append(row[3])

close1.append(row[4])

print(close1[1])

k = 0

inputmatrix1 = []

inputmatrix2 = []

inputmatrix3 = []

eigenvectormatrix1 = []

eigenvectormatrix2 = []

eigenvectormatrix3 = []

for num in range(1, 30):

temp1 = Matrix([[close1[k+num],close1[k+num+1],close1[k+num+2]],[close1[k+num+1],close1[k+num+2],0],[close1[k+num+2],0,0]])

temp2 = Matrix([[close1[k+num+1],close1[k+num+2],close1[k+num+3]],[close1[k+num+2],close1[k+num+3],0],[close1[k+num+3],0,0]])

temp3 = Matrix([[close1[k+num+2],close1[k+num+3],close1[k+num+4]],[close1[k+num+3],close1[k+num+4],0],[close1[k+num+4],0,0]])

print("debug1")

inputmatrix1.append(temp1)

inputmatrix2.append(temp2)

inputmatrix3.append(temp3)

print("debug2")

editedinputmatrix1 = temp1.T*temp1

editedinputmatrix2 = temp2.T*temp2

editedinputmatrix3 = temp3.T*temp3

print("debug3")

print(editedinputmatrix1.eigenvects())

print(editedinputmatrix2.eigenvects())

print(editedinputmatrix3.eigenvects())

eigenvectormatrix1.append(editedinputmatrix1.eigenvects())

eigenvectormatrix2.append(editedinputmatrix2.eigenvects())

eigenvectormatrix3.append(editedinputmatrix3.eigenvects())

print(num)

print(editedinputmatrix3.eigenvects())

print(eigenvectormatrix3)

[Vinzent Steinberg]

On Monday, February 10, 2014 11:27:09 PM UTC-5, monde wilson wrote:

why eigenvectors very slow

what is the difference between numpy and sympy when doing matrix calculation

Sympy calculates eigenvectors symbolically (thus exactly), numpy calculates them numerically using floating point arithmetic.

In general you don't want to use sympy to calculate the eigenvectors for matrices larger than 2x2, because the symbolic results can be very complicated. (IIRC, the eigenvalues are calculated by finding roots of the characteristic polynomial, which can lead to nasty expressions for dimension 3 and beyond.)

 

will numpy faster and more accurately

Numpy will be a lot faster, but not more accurate. If you only need numerical results, you probably should use numpy for this.

Vinzent

[刘金国]

4 x 4 is needed ~~
mathematica runs extremely fast for 4 x 4 matrix as it should be, but ...

在 2014年2月12日星期三 UTC+8上午5:40:19，Vinzent Steinberg写道：

[Ondřej Čertík]

Hi,

On Fri, Jul 10, 2015 at 7:30 AM, 刘金国 <cacat...@gmail.com> wrote:
> 4 x 4 is needed ~~
> mathematica runs extremely fast for 4 x 4 matrix as it should be, but ...

Can you post the Mathematica result? So that we know what you are
trying to get and we can then help you get it with SymPy.

Ondrej

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/62a17328-bcd2-4955-9534-ae5358e89041%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Jacob Miner]

If I wanted to get the eigenvectors (and eigenvalues) of a 10x10 symbolic matrix that is relatively sparse, is it possible to use sympy to solve this issue? Can the eigenvects() operation be parallelized in any way?

I am trying to use OCTAVE as well (which calls from sympy), but once I get above 4x4 the time required to get a solution seems to scale geometrically: (2x2 in <1 sec, 3x3 in ~2 sec, 4x4 in ~minutes, 5x5 ~hr, 7x7 ~12 hr).

Is there some code somewhere with a robust eigensolver that can generate the eigenfunctions and eigenvalues of a 10x10 symbolic matrix? Based on my 7x7 matrix I know the denominators of the solution can be huge, but this is an important problem that I need to solve.

Thanks.

[Aaron Meurer]

How sparse is the matrix, and what do the entries look like?

One thing that can help depending on what your matrix looks like is to
replace large subexpressions with symbols (if there are common
subexpressions, cse() can help with this). That way the simplification
algorithms don't get caught up trying to simplify the subexpressions.
However if you expect the subexpressions to cancel each other out in
the result, this can be detrimental.

I would start with the eigenvalues. Once you can get those, you will
want to simplify them if possible, before computing the eigenvectors.

Aaron Meurer

> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/d95a66fe-9135-4365-9386-6641bf51d9fa%40googlegroups.com.

[Jacob Miner]

I will show you a representation of the 7x7 form of my matrix, the 10x10 includes a couple additional elements, but has the same overall structure and layout.

The key point is that the diagonal elements are differences of multiple values, and each of these values occupies a certain element in the lower left of the matrix - the upper right is all 0s. The last two columns are also all 0s.

It is not really possible to simplify it further.

>>> woVIt = Matrix([[-(k+kcSD),0,0,0,0,0,0],[k,-(kEI+kcED),0,0,0,0,0],[0,kEI,-(kIH+kIR+kcID),0,0,0,0],[0,0,kIH,-(kHHt+kHD+kHR+kcHD),0,0,0],[0,0,0,kHHt,-(kHtD+kHtR),0,0],[kcSD,kcED,kcID,(kHD+kcHD),kHtD,0,0],[0,0,kIR,kHR,kHtR,0,0]])

>>> woVIt.eigenvals()
{0: 2, -kIH - kIR - kcID: 1, -kHD - kHHt - kHR - kcHD: 1, -k - kcSD: 1, -kEI - kcED: 1, -kHtD - kHtR: 1}

>>> woVIt.eigenvects()
[(0, 2, [Matrix([
[0],
[0],
[0],
[0],
[0],
[1],
[0]]), Matrix([
[0],
[0],
[0],
[0],
[0],
[0],
[1]])]), (-k - kcSD, 1, [Matrix([
[                                                                      -(k + kcSD)*(k - kEI - kcED + kcSD)*(k - kHtD - kHtR + kcSD)*(k - kIH - kIR - kcID + kcSD)*(k - kHD - kHHt - kHR - kcHD + kcSD)/(k*kEI*(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD)))],
[                                                                                                 (k + kcSD)*(k - kHtD - kHtR + kcSD)*(k - kIH - kIR - kcID + kcSD)*(k - kHD - kHHt - kHR - kcHD + kcSD)/(kEI*(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD)))],
[                                                                                                                                    -(k + kcSD)*(k - kHtD - kHtR + kcSD)*(k - kHD - kHHt - kHR - kcHD + kcSD)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD))],
[                                                                                                                                                                      kIH*(k + kcSD)*(k - kHtD - kHtR + kcSD)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD))],
[                                                                                                                                                                                         -kHHt*kIH*(k + kcSD)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD))],
[(k*kEI*kHHt*kHtD*kIH - (k*kEI*kIH*(kHD + kcHD) - (k*kEI*kcID - (k*kcED - kcSD*(k - kEI - kcED + kcSD))*(k - kIH - kIR - kcID + kcSD))*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD))/(k*kEI*(kHHt*kHtR*kIH - (kHR*kIH - kIR*(k - kHD - kHHt - kHR - kcHD + kcSD))*(k - kHtD - kHtR + kcSD)))],
[                                                                                                                                                                                                                                                                                                            1]])]), (-kEI - kcED, 1, [Matrix([
[                                                                                                                                                                                                                                                                                                                                                                                                        0],
[                                                                                                                                                                                 (kEI + kcED)*(kEI - kHtD - kHtR + kcED)*(kEI - kIH - kIR + kcED - kcID)*(kEI - kHD - kHHt - kHR + kcED - kcHD)/(kEI*(kHHt*kHtR*kIH - (kHR*kIH - kIR*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED)))],
[                                                                                                                                                                                                                      -(kEI + kcED)*(kEI - kHtD - kHtR + kcED)*(kEI - kHD - kHHt - kHR + kcED - kcHD)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED))],
[                                                                                                                                                                                                                                                          kIH*(kEI + kcED)*(kEI - kHtD - kHtR + kcED)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED))],
[                                                                                                                                                                                                                                                                               -kHHt*kIH*(kEI + kcED)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED))],
[(kEI*kHHt*kHtD*kIH*(-k + kEI + kcED - kcSD) - (kEI*kIH*(kHD + kcHD)*(-k + kEI + kcED - kcSD) - (kEI*kcID*(-k + kEI + kcED - kcSD) - kcED*(-k + kEI + kcED - kcSD)*(kEI - kIH - kIR + kcED - kcID))*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED))/(kEI*(kHHt*kHtR*kIH - (kHR*kIH - kIR*(kEI - kHD - kHHt - kHR + kcED - kcHD))*(kEI - kHtD - kHtR + kcED))*(-k + kEI + kcED - kcSD))],
[                                                                                                                                                                                                                                                                                                                                                                                                        1]])]), (-kHtD - kHtR, 1, [Matrix([
[                  0],
[                  0],
[                  0],
[                  0],
[-(kHtD + kHtR)/kHtR],
[          kHtD/kHtR],
[                  1]])]), (-kIH - kIR - kcID, 1, [Matrix([
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          0],
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          0],
[                                                                                                                                                                                                                                                                                                      -(kIH + kIR + kcID)*(-kHtD - kHtR + kIH + kIR + kcID)*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID))*(-kHtD - kHtR + kIH + kIR + kcID))],
[                                                                                                                                                                                                                                                                                                                                                 kIH*(kIH + kIR + kcID)*(-kHtD - kHtR + kIH + kIR + kcID)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID))*(-kHtD - kHtR + kIH + kIR + kcID))],
[                                                                                                                                                                                                                                                                                                                                                                             -kHHt*kIH*(kIH + kIR + kcID)/(kHHt*kHtR*kIH - (kHR*kIH - kIR*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID))*(-kHtD - kHtR + kIH + kIR + kcID))],
[(kHHt*kHtD*kIH*(-k + kIH + kIR + kcID - kcSD)**2*(-kEI + kIH + kIR - kcED + kcID) - (kIH*(kHD + kcHD)*(-k + kIH + kIR + kcID - kcSD)**2*(-kEI + kIH + kIR - kcED + kcID) - kcID*(-k + kIH + kIR + kcID - kcSD)**2*(-kEI + kIH + kIR - kcED + kcID)*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID))*(-kHtD - kHtR + kIH + kIR + kcID))/((kHHt*kHtR*kIH - (kHR*kIH - kIR*(-kHD - kHHt - kHR + kIH + kIR - kcHD + kcID))*(-kHtD - kHtR + kIH + kIR + kcID))*(-k + kIH + kIR + kcID - kcSD)**2*(-kEI + kIH + kIR - kcED + kcID))],
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          1]])]), (-kHD - kHHt - kHR - kcHD, 1, [Matrix([
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      0],
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      0],
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      0],
[                                                                                                                                                                                                                           (kHD + kHHt + kHR + kcHD)*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kHtD - kHtR + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID)/(kHHt*kHtR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID) - kHR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kHtD - kHtR + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID))],
[                                                                                                                                                                                                                                                             -kHHt*(kHD + kHHt + kHR + kcHD)*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID)/(kHHt*kHtR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID) - kHR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kHtD - kHtR + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID))],
[(kHHt*kHtD*(-k + kHD + kHHt + kHR + kcHD - kcSD)**3*(-kEI + kHD + kHHt + kHR - kcED + kcHD)**2*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID) - (kHD + kcHD)*(-k + kHD + kHHt + kHR + kcHD - kcSD)**3*(-kEI + kHD + kHHt + kHR - kcED + kcHD)**2*(kHD + kHHt + kHR - kHtD - kHtR + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID))/((kHHt*kHtR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID) - kHR*(-k + kHD + kHHt + kHR + kcHD - kcSD)*(-kEI + kHD + kHHt + kHR - kcED + kcHD)*(kHD + kHHt + kHR - kHtD - kHtR + kcHD)*(kHD + kHHt + kHR - kIH - kIR + kcHD - kcID))*(-k + kHD + kHHt + kHR + kcHD - kcSD)**2*(-kEI + kHD + kHHt + kHR - kcED + kcHD))],
[                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      1]])])]

So that is the issue - I cannot really simplify the eigenvalues, and I am still not sure how to proceed.

Any ideas?

Thank you.

[Isuru Fernando]

Hi,

For triangular matrices, it's straightforward to calculate eigenvectors. You just need triangular solves. See Section 4.4.1 of Heath's Scientific Computing 2nd Edition.

Isuru

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/45532240-28a4-49ac-80d4-4df276ab1f81%40googlegroups.com.

[Aaron Meurer]

Your matrix is far simpler than I had imagined (you should have
mentioned that it was triangular). I think as Isuru said we can likely
implement a faster method for triangular matrices. The eigenvalues
themselves (the diagonals) are already computed very quickly.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CA%2B01voMMNUm2PXZ76nKto6_wQRmdWGLXaE0wu92YEcjjrT1r5A%40mail.gmail.com.

[Jacob Miner]

Isuru,

I went into Heath's text to get your reference, and it helps layout the method, but can you please clarify what you meant by 'triangular solves'?

Thank you.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6L%2B8nkg_JbUtSUP_xf52GHWHRJxAc%2B_L4kshn%3Dp4pqmaw%40mail.gmail.com.

[Isuru Fernando]

First k-1 entries of the k th eigenvector for an upper triangular matrix U is U[:k-1,:k-1]^-1 @ U[:k-1,k], which is a triangular solve since U[:k-1,:k-1] is a triangular matrix and it can be done in O(k^2) time.

Isuru

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CALO0EbvUt8UGMM6eo7bKXkWXcorX_yVP3%3D4qkHLwhoQ3iLtKzw%40mail.gmail.com.

[Jacob Miner]

I think I understand, but is there an implementation of this technique that can actually perform the linear algebra on a symbolic matrix at such improved compute-time?