Linked Questions
12 questions linked to/from full rank update to cholesky decomposition
3
votes
1
answer
953
views
Clever ways to update LU factorization for ridge regression [duplicate]
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 ...
- 155
23
votes
3
answers
3k
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 ...
- 3,909
4
votes
1
answer
1k
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 ...
- 41
21
votes
1
answer
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 ...
luogyong
2
votes
1
answer
3k
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
...
- 227
5
votes
2
answers
1k
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
2
answers
2k
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 ...
- 792
4
votes
2
answers
264
views
Is there a simple way to add a sparse matrix to an LU decomposition of a dense matrix?
I am solving a parabolic equation in the form:
$$
\left( {M \over\tau_j} + A \right) u^{j+1} = M f^j + {u^j \over \tau_j},
$$
where $A$ and $f$ are a dense stiffness matrix and the right hand side of ...
- 183
7
votes
1
answer
937
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, ...
- 375
6
votes
2
answers
206
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-...
- 163
5
votes
1
answer
387
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^...
- 870
3
votes
1
answer
475
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 ...
- 8,602