Efficient Matrix Precomputation

Question

Assume two $n \times n$ matrices $A$ and $B$ are known before hand and any precomputation can be done on them. Is there an efficient way to solve a set of linear problems: $$ \begin{split} (A+w_1 B) x_1 &= y_1, \\ (A+w_2 B) x_2 &= y_2, \\ &\vdots \end{split} $$ where $w_1, w_2, \dotsc$ are diagonal matrices (weights of a set of constraints), $x_1, x_2, \dotsc$ are unknown vectors and $y_1, y_2, \dotsc$ are right hand side vectors.

If $w_1 = w_2 = \dotsb = w$, then we can LU decompose $A+w B$ and simply solve for all $x_i$. Now the problem is that $w_1, w_2, \dotsc$ are different. So do I have to solve each problem individually or is there a more efficient way?

Answer 1

If the $w_i$ are scalars (multiples of the identity matrix), then you can use a generalized Schur factorization of $(A,B)$ to solve the problem in $O(n^3+kn^2)$, where $k$ is the number of different weights: just compute $A=QTZ, B=QSZ$, where $Q,Z$ are orthogonal and $T,S$ triangular, and then each system with $A+w_i B = Q(T+w_iS)Z$ can be solved in $O(n^2)$ because you have a factorization of the matrix as a product of orthogonal and triangular matrices.

If all the $w_i$ are multiples of the same invertible matrix $D$ you can adapt this trick by premultiplying each system by $D$.

If the $w_i$s have only at most $h$ nonzeros, there are different techniques to solve each system in $O(nh^2)$ (look for low rank updates of matrix factorizations).

For general diagonal $w_i$s, I am afraid that the answer is no. The same problem with $B=I$ appears in several applications, and for instance it gets asked a lot on [scicomp.se], so I would be surprised if there was a trick that I have never seen to do it.