7
$\begingroup$

I'm using a numeric root-finder to find $k$ satisfying $\|A^k x\|=c$ where $A$ is a symmetric $d\times d$ diagonal + rank-1 matrix. How to compute $A^k x$ efficiently?

  • For integer $k$, I can get the answer in $O(k d)$ time using iterated products.
  • For general $k$, can use dense eigendecomposition of $A$ in $O(d^3)$ time
  • Is there a way to do it faster than $O(d^3)$ for general $k$?

My $d\approx 10000$, $k\in(1,10000)$

$\endgroup$

1 Answer 1

8
$\begingroup$

This paper shows an algorithm to compute the eigendecomposition of symmetric diagonal-plus-rank-1 matrices in $O(d^2)$.

$\endgroup$
4
  • $\begingroup$ Interesting that they don't reuse work between eigenvectors, procedure is called $d$ times independently. $\endgroup$ Feb 22, 2023 at 22:39
  • 1
    $\begingroup$ Found some Matlab code from a different paper as dpr1eig.m in zenodo.org/record/7338121#.Y_eoEezMK0p $\endgroup$ Feb 23, 2023 at 17:53
  • 1
    $\begingroup$ I posted this question on mathematica.SO where Henrik Schumacher gave an explanation of approaches and an implementation of Stor's paper. $\endgroup$ Feb 28, 2023 at 20:34
  • 1
    $\begingroup$ By coincidence, I encountered this paper that pursues the eigendecomposition of a unitary plus rank-1 matrix in O(n) space / O(n^2) time. I don't think this captures the OP's use case, but I leave it here in the hope a future reader might find it useful: Aurentz, Jared L., et al. "Fast and backward stable computation of roots of polynomials." SIAM Journal on Matrix Analysis and Applications 36.3 (2015): 942-973. $\endgroup$ Mar 10, 2023 at 21:35

Your Answer

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

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