Skip to main content
1 of 2
Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120

No. It is hard to prove a negative, but this question (and variants) get asked a lot on [scicomp.se], and the answer is invariably that there is no technique to do it; see for instance this answer.

If this were possible, many practically-relevant algorithms such as rational Krylov algorithm would have a significant speed-up, so people have definitely been working on related themes and found nothing yet.

The closest thing you can do is performing a $O(n^3)$ precomputation on a symmetric positive definite matrix $M=M^*$ that lets you solve, in time $O(n)$ each, linear systems of the form $M+\alpha_k I$, for many values $\alpha_1,\dots,\alpha_m$: reduce $M$ to tridiagonal form, and use a tridiagonal solver.

Tridiagonal reduction, i.e., finding an orthogonal $Q$ such that $M=QTQ^*$, with $T$ tridiagonal, is a part of algorithms to compute eigenvalues and is available in Lapack and most languages.

For a nonsymmetric matrix you can use the same trick with Hessenberg reduction rather than tridiagonal, getting $O(n^3+mn^2)$.

Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120