Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to compute the maximum eigenvalue of a diagonal plus rank-one matrix. Are there fast algorithms for the computation of the largest eigenvalue? What is the computational complexity of those algorithms?

share|improve this question
    
Are you familiar with the power method? This is the simplest way to approximate the dominant eigenvalue, requiring a simple sequence of matrix-vector multiplications (with scaling as needed to keep the results within a range of floating point exponents). Here you have the advantage of doing the matrix-vector multiplies with $O(n)$ arithmetic in each step. –  hardmath Sep 27 '13 at 10:36
    
I am familiar with the power method, but I think that the special structure can be exploited somehow. I guess that this structure may have been considered before in the literature. –  lbla Sep 27 '13 at 10:59
    
A normal (dense) matrix-vector multiply is $O(n^2)$, so you would be exploiting the special structure of your matrix by reducing this operation cost to $O(n)$. If you are hoping the special form allows you to solve directly for eigenvalues, I do not think what you've described so far allows this. –  hardmath Sep 27 '13 at 11:14
    
Here's another request: Are your diagonal-plus-rank-one matrices symmetric? I assumed not since you didn't specify, but it makes things a bit easier if they were symmetric. –  hardmath Sep 28 '13 at 5:43
add comment

1 Answer 1

up vote 1 down vote accepted

The numerical eigenvalue problem for diagonal-plus-rank-one (DPR1) matrices has been considered in the literature, often in a broader context of algorithms for generalized companion matrices.

Typical of these is the recent paper "Accurate eigenvalue decomposition of arrowhead matrices and applications," by N.J. Stor, I. Slapnicara, J. Barlow (arXiv.org, 2013), cf. Sec. 6.3 where the real-symmetric DPR1 eigenvalue problem for $D + uu^T$ is treated (and according to Remark 5 a more general such case is the subject of a forthcoming paper).

Slightly older but perhaps more germane (treating the nonsymmetric case) is the paper "Fast and Stable QR eigenvalue algorithms for generalized companion matrices and secular equations," by Bini, Gemignani, and Pan, Numer. Math. (2005), which gives details of an $O(n^2)$ operation, $O(n)$ space method for finding all eigenvalues to high relative precision by a structure preserving variant of QR steps.

As noted in my Comments above, a power iteration for determining a dominant eigenvalue can take advantage of the special structure of DPR1 matrices in forming matrix-vector products with $O(n)$ operation cost, a significant improvement over the usual $O(n^2)$ cost for matrix-vector products.

This advantage carries over to more sophisticated algorithms which accelerate convergence (by shift & invert) or which improve stability via orthogonal transforms (as with QR; see above). Note that the shift of a DPR1 matrix is DPR1, and the inverse of an invertible DPR1 matrix is again DPR1.

Added: In the special case $D=I$ the eigenvalues/eigenvectors of $I + vu^T$ can be explicitly expressed, just as a spectrum shift for rank one matrix $vu^T$. That is, $(I+vu^T)u = (v\cdot u + 1) u$, and for any $w\cdot u = 0$, then $(I+uv^T)w = w$. The largest eigenvalue $\lambda$ is then $v\cdot u + 1$ or $1$ depending on the sign of $v\cdot u$.

Standard treatments of estimating the largest eigenvalue of a positive definite symmetric matrix often begin with a reduction to tridiagonal form, either by full similarity transformation or by a Lanczos type approximation of smaller dimension. Because the DPR1 structure is already of $O(n)$ size, there is no need for tridiagonal reduction, and instead one can immediately begin searching for the largest eigenvalue (at least in the symmetric case) through evaluations of $\det(\lambda I - (D+uu^T))$.

Provided $\lambda$ differs from any of the entries on diagonal $D$, $\lambda I - D$ is invertible/has nonzero determinant and can be factored out, leaving us with evaluation of $\det(I - wu^T)$ where $w = (\lambda I - D)^{-1} u$. The material discussed in the first added paragraph above can be recast as an explicit characteristic polynomial, and in particular, if $w\cdot u \neq 0$:

$$ \det(I - wu^T) = 1 - w\cdot u $$

whose evaluation has cost $O(n)$.

share|improve this answer
    
The diagonal matrix D is not the identity and, in general, the entries of the diagonal are all different. –  lbla Oct 8 '13 at 10:38
    
Not everything I added above depends on $D$ being the identity, as for example the evaluation of the determinant can be done in $O(n)$ without assuming anything other than $D$ invertible. Is the matrix symmetric? Positive definite? –  hardmath Oct 8 '13 at 11:15
1  
The matrix D is positive definite –  lbla Oct 11 '13 at 17:11
    
Okay, the diagonal part is positive definite (symmetric), but the rank one part is not necessarily symmetric (and the combination is not necesssarily positive definite symmetric)? –  hardmath Oct 11 '13 at 18:14
1  
The matrix is of the type D + uu' –  lbla Oct 15 '13 at 8:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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