Linked Questions

22
votes
3answers
2k views

Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices? For example, if each $D_i$ is ...
21
votes
1answer
3k views

Diagonal update of a symmetric positive definite matrix

$A$ is a $n \times n$ symmetric positive definite (SPD) sparse matrix. $G$ is a sparse diagonal matrix. $n$ is large ($n$ >10000) and the number of nonzeros in the $G$ is usually 100 ~ 1000. $A$ has ...
4
votes
1answer
545 views

LU Decomposition of PSD Matrix + Diagonal Matrix

If I have a psd, symmetric matrix $\mathbf{A}$ and I need to do LU decomps on $\mathbf{B_i}= \mathbf{A} + \mathbf{D_i}$ (where $\mathbf{D_i}$ is a diagonal psd matrix, where $\mathbf{D_i}$ changes ...
5
votes
2answers
574 views

Perturbation of Cholesky decomposition for matrix inversion

I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$ where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...
4
votes
2answers
1k views

Computational complexity and implementation of UDU Modified Cholesky Rank 1 Update

I am attempting to increase the performance of a legacy Kalman Filter implementation. The state covariance is factored in terms of UDU, i.e. $\mathbf{P} = \mathbf{U}\mathbf{D}\mathbf{U}^T$. Many ...
1
vote
1answer
819 views

Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates

I want to solve the time-dependent Schrodinger Equation using the Crank-Nicolson scheme. I end up with the following matrix equation ...
1
vote
1answer
570 views

Clever ways to update LU factorization for ridge regression

Ridge regression can be posed as minimizing the following objective function (over $x$): $$\frac{1}{2} \lVert Ax - b \lVert_2^2 ~+ \frac{\lambda}{2} \lVert x \lVert_2^2 $$ Which has a closed form ...
5
votes
1answer
325 views

Solving $ (A^{-1} + D)^{-1} v $ with low rank Cholesky factors of $A$

I have a large matrix $A \in \mathcal{R}^{N\times N}$ which is supposedly positive-definite, but numerically low rank. Instead of $A$, I have its incomplete Cholesky factor $G$, such that $A \simeq GG^...
4
votes
0answers
482 views

full rank update to cholesky decomposition for multivariate normal distribution

This question is a specialization of full rank update to cholesky decomposition, to which I hope to get a more positive answer. When calculating the minus log of the multivariate normal distribution, ...
6
votes
2answers
123 views

Efficient approach for solving matrix plus diagonal matrix system that varies in time

When solving a system of ODEs, as part of a preconditioner, I get the system $(A + D(t))x = b(t)$ where $A$ is a sparse matrix and $D(t)$ is diagonal. I'm currently solving this by taking the LU-...
2
votes
1answer
132 views

Re-using LU factorization within iterative (?) setup for a sum of two matrices

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...