7
$\begingroup$

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?)

How about sparse matrices? What are the best known algorithms for finding eigenvalues/eigenvectors of a matrix which is exponential in the input size (number of non-zero entries)?

In general, is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or rather, not known to be computationally easy?

  • 0
    Thanks a lot Kaveh! That was exactly what I wanted to know. Actually, this case had occurred to me - I just wasn't sure what notions still make sense, but apparently people have papers about this, which I am now reading.2011-07-11

0 Answers 0