Operating Time for Matrix

1. Sep 13, 2011

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

2. Sep 13, 2011

chiro

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.

3. Sep 13, 2011

Cylab

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()?

4. Sep 13, 2011

chiro

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.

5. Sep 13, 2011

AlephZero

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(n3) operations.

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

6. Sep 13, 2011

Cylab

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

7. Sep 13, 2011