5
$\begingroup$

What is a good direct method to compute the spectral decomposition / Schur decomposition / singular decomposition of a symmetric matrix?

"Direct" means as in LU decomposition, Cholesky decomposition, or Golub's SVD algorithm, in contrast to iterative methods.

You can, of course, apply the aforementioned algorithm of Golub, but I guess that would be breaking a butterfly on a wheel.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

In addition to the QR algorithm, the divide and conquer method is also worth mentioning. It is applicable to symmetric tridiagonal matrices, but any matrix can be reduced to such a form via the Lanczos method*. It hinges on the observation that a tridiagonal matrix is, up to a rank 1 perturbation, a block diagonal matrix. One can then find the eigendecomposition of the sub-blocks (in parallel!) and glue them back together using a clever trick. Of course, finding the eigenvalues of the blocks must be done with the QR method as Federico alludes to.

However, you've asked for a direct method -- both QR and divide and conquer are iterative methods. Well, there is no direct method akin to the LU decomposition to find the eigendecomposition of a matrix of dimension greater than 5, there are only iterative methods. If such a direct method existed, one could find the zeros of an arbitrarily high-degree polynomial as an algebraic function of the coefficients, which Galois told us is impossible. The Golub-Kahan SVD algorithm is also iterative.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The distinction between direct and iterative seems quite ill-posed, indeed. I took it as "no Arnoldi". $\endgroup$
    – Federico Poloni
    Jun 14, 2014 at 13:13
  • $\begingroup$ Thank you for clarifying this to me. @FedericoPolini: I take non-iterative as 'produces the result for an n x n matrix in f(n) steps, where f(n) is some function'. See the contrast between LU decomposition and Jacobi iteration. But even if one accepts this: Some recommend applying a Jacobi iteration after an LU-decomposition based solver. So one may regard this as one algorithm of two phases. $\endgroup$
    – shuhalo
    Jun 14, 2014 at 16:53
  • $\begingroup$ I don't think your argument is strictly correct: first, using Galois theory there can be shown not to exist a general radical function of the coefficients, which is a very special form of an algebraic function. Second, I don't see how a direct method for the decomposition would necessarily lead to a radical function to obtain the roots for the coefficients: it depends a bit on what you mean by non-iterative evaluation, but if you want to allow using sin, sqrt, log etc there exist non-iterative ways to express the roots of a polynomial in its coefficients (at least for degree 5). $\endgroup$
    – doetoe
    Jun 17, 2014 at 13:26
  • $\begingroup$ E.g. for the quintic there is a general expression in transcendental functions of the coefficients that can be evaluated as floating point numbers in constant time. This is desribed explicitly here: en.wikipedia.org/wiki/… and here: mathworld.wolfram.com/QuinticEquation.html $\endgroup$
    – doetoe
    Jun 17, 2014 at 13:27
1
$\begingroup$

The implicit (Francis) QR iteration, with several additional tricks, is the standard algorithm. I suggest you to check a book such as Watkins' The Matrix Eigenvalue Problem for details; this is a classical topic.

(I find it unusual that you are familiar with Golub's SVD but not with QR - the two methods are similar and usually taught together).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.