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)$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting that they don't reuse work between eigenvectors, procedure is called $d$ times independently. $\endgroup$
    – Yaroslav Bulatov
    Feb 22 at 22:39
  • 1
    $\begingroup$ Found some Matlab code from a different paper as dpr1eig.m in zenodo.org/record/7338121#.Y_eoEezMK0p $\endgroup$
    – Yaroslav Bulatov
    Feb 23 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$
    – Yaroslav Bulatov
    Feb 28 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$
    – rchilton1980
    Mar 10 at 21:35

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.