Operating Time for Matrix Eigenvalue and Eigenvectors

[Cylab]

Hello

Assume matrix A (r*r), and calculate eigenvalue and eigenvectors by using Jordan matrix form.
So how should I find the Operating Time O(?) for it?

Will you please provide some analysis for it? like how should it be calculated etc.

Thanks

 

[chiro]

Hello

Assume matrix A (r*r), and calculate eigenvalue and eigenvectors by using Jordan matrix form.
So how should I find the Operating Time O(?) for it?

Will you please provide some analysis for it? like how should it be calculated etc.

Thanks

If you need to find a general determinant (or at least an expression for the eigenvalues), then this will be O(n!) (by O I mean Big-O) where n is the rank of the matrix. (I got this from wikipedia in case you are interested).

In terms of finding the eigenvalues, you will probably use a root finding algorithm, especially if you can't guarantee small enough n. The time for this varies depending on the algorithm and the function in question.

In terms of calculated the Big-O for the determinant, you can use the inductive definition to help you prove the Big-O for that. For the other parts I can't help you.

 

[Cylab]

Thanks Chiro for your analysis..
BTW, what is n in O(n!) ? Is it r*r = n?

Will there be any way of increasing performance by reducing Operation time O()?

 

[chiro]

Thanks Chiro for your analysis..
BTW, what is n in O(n!) ? Is it r*r = n?

Will there be any way of increasing performance by reducing Operation time O()?

The O(n!) is the Big-O notation for computational complexity. The n is your r (the rank of the matrix).

As for increasing performance, the answer is "it depends".

If you know the size of your matrix in advance, you can create an optimized hard-coded routine for this. This kind of things happens in many applications including video games, rendering software, and scientific software.

Apart from that, you might be able to do further optimizations if the matrix in question has a particular structure. For example if its lower or upper triangular, the determinant is just the product of the diagonal elements and that is a lot quicker than using the general formula. So if you "knew" things in advance, you could use this to your advantage.

 

[AlephZero]

If you need to find a general determinant (or at least an expression for the eigenvalues), then this will be O(n!) (by O I mean Big-O) where n is the rank of the matrix. (I got this from wikipedia in case you are interested).

You didn't give a page reference to where you found that in Wikipedia, but it doesn't look right.

The time to calculate a determinant by summing up all the permutations might well be O(n!), but that is a very inefficient way to do it. If you use row operations to reduce the matrix to an upper (or lower) triangular form with the same determinant, the determinant of the triangular matrix is just the product of the diagonal terms, and the whole process will take O(n³) operations.

Efficient algorithms to calculate all the eigenvalues and vectors of a matrix also take O(n³) operations.

 

[Cylab]

Can　you tell me how your suggested stuff affect matrix `s performance of generating eigenvalues and eigenvectors? or simply operation time?

 

[Cylab]

You didn't give a page reference to where you found that in Wikipedia, but it doesn't look right.

The time to calculate a determinant by summing up all the permutations might well be O(n!), but that is a very inefficient way to do it. If you use row operations to reduce the matrix to an upper (or lower) triangular form with the same determinant, the determinant of the triangular matrix is just the product of the diagonal terms, and the whole process will take O(n³) operations.

Efficient algorithms to calculate all the eigenvalues and vectors of a matrix also take O(n³) operations.

Thanks for your attention. please let me give an example.
E.g. Matrix (3*3) => then has to be 3 eigenvectors (right?): v_1, v_2.v_3, but eigenvalues can λ_1 or λ_1 and λ_2 or λ_1, λ_2 and λ_3. Thus, why operation time O(n³) {n=3}? Could you please give me some calculation hint? thanks.

 

[chiro]

You didn't give a page reference to where you found that in Wikipedia, but it doesn't look right.

The time to calculate a determinant by summing up all the permutations might well be O(n!), but that is a very inefficient way to do it. If you use row operations to reduce the matrix to an upper (or lower) triangular form with the same determinant, the determinant of the triangular matrix is just the product of the diagonal terms, and the whole process will take O(n³) operations.

Efficient algorithms to calculate all the eigenvalues and vectors of a matrix also take O(n³) operations.

Yeah I didn't look at the optimal methods, only the standard inductive based calculation:
http://en.wikipedia.org/wiki/Determinant (you can find a comparison of optimal with inductive techniques where it compares O(n^3) with O(n!)).

If the OP is interested in references to the techniques AlephZero is describing look at the link to see more information.