7

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

Yaroslav Bulatov
  • 2,655
  • 11
  • 23

1 Answers1

8

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

Federico Poloni
  • 11,344
  • 1
  • 31
  • 59
  • Interesting that they don't reuse work between eigenvectors, procedure is called $d$ times independently. – Yaroslav Bulatov Feb 22 '23 at 22:39
  • 1
    Found some Matlab code from a different paper as dpr1eig.m in https://zenodo.org/record/7338121#.Y_eoEezMK0p – Yaroslav Bulatov Feb 23 '23 at 17:53
  • 1
    I posted this question on mathematica.SO where Henrik Schumacher gave an explanation of approaches and an implementation of Stor's paper. – Yaroslav Bulatov Feb 28 '23 at 20:34
  • 1
    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. – rchilton1980 Mar 10 '23 at 21:35