4
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.