Questions tagged [matrix-factorization]
The matrix-factorization tag has no usage guidance.
2
votes
0answers
61 views
Numerical analysis, pivoting and incomplete LU decomposition
When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
4
votes
1answer
86 views
Numerically find the nearest positive semi definite matrix to a symmetric matrix
I have a symmetric matrix $M$ which I want to numerically project onto the positive semi definite cone.
To do so, I decompose it into $M = QDQ^T$ and transform all negative eigenvalues to zero. (...
3
votes
0answers
96 views
Factorize laplacian in terms of first derivative matrix
I am trying to factorize the following Laplacian matrix in terms of $ D^TD$, D is the first derivative matrix.
The tridiagonal form of the secon derivative matrix using Neumann boundary condition is ...
-4
votes
1answer
86 views
what is Sherman-Morrison formula
Can someone please explain what is the Sherman-Morrison formula and it's specialities when it comes to matrix calculations? I'm a little bit confused on understanding how the preconditioning works ...
4
votes
2answers
119 views
Factoring the sum of two matrices
Given
\begin{equation}
A_i=B+C_i
\end{equation}
where $A_i$,$B$ and $C_i$, $i=1,\dotsc,N$ are large square matrices, $B$ is symmetric, $C_i$ are zero matrices aside for a square block on the diagonal.
...
5
votes
2answers
99 views
Term for the typical “linear in the larger dimension, quadratic in the smaller” cost for linear algebra
Many dense linear algebra decompositions (QR, SVD...) on an $m\times n$ matrix have cost
$$
O(\max(m,n)\min(m,n)^2)
$$
when implemented in practice on a computer. Is there a colloquial name or a more ...
3
votes
0answers
34 views
Reweighted least squares factorization
This is a continuation of the question asked here. I want to solve numerous least squares systems of the form
$$
D_i A x \approx D_i b
$$
where $D_i$ are $m \times m$ diagonal matrices with positive ...
1
vote
1answer
223 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
...
6
votes
2answers
244 views
inertia count sparse matrix with dense low-rank perturbation
I would like to determine the number of negative eigenvalues (inertia count) of the $(N \times N)$ symmetric real matrix $K - \sigma M$, with $K$ a positive-definite sparse matrix and $M$ a positive-...
7
votes
1answer
173 views
Least Squares with Dense-Block Diagonal Structure
I need to solve a least squares problem that takes the following form:
$$p = \arg \min_{x}\Vert J V x - y \Vert_2, $$
where $J \in \mathbb{R}^{N \times N}$ is a general dense matrix, and $V \in \...
2
votes
1answer
102 views
How we can use CUR decomposition in place of SVD decomposition?
I have understood how CUR and SVD works, but have not been able to understand the following.
How can we use CUR in place of the SVD decomposition?
Do the $C$ and $R$ matrices in the CUR follow the ...
1
vote
0answers
58 views
Stable Method of orthogonal projection onto a subspace with the help of Moore-Penrose inverse,
Projection of a vector $v$ onto the column space of a matrix $A$ is given by $AA^\dagger v$. From the definition of Moore-Penrose Inverse we know that $AA^\dagger v = (A^T)^\dagger A^T v $.
Below is ...
0
votes
1answer
79 views
Matrix factorization empty rows and columns
I would like to do non negative mf and I wanna ask a question about my main matrix. The question is should I include rows and columns that have no non-zero entry in them. I think if there is not a ...
1
vote
1answer
113 views
Supernodal vs multifrontal factorizations
What are the differences between supernodal and multifrontal matrix factorizations? Can you provide a few references or high-level points about the approaches?
14
votes
4answers
240 views
Rapidly determining whether or not a dense matrix is of low rank
In a software project that I'm working on, certain computations are vastly easier for dense low-rank matrices. Some problem instances involve dense low-rank matrices, but they're given to me in full, ...
1
vote
1answer
145 views
Matrix Decomposition of Conics
I was reading about ellipse-ellipse intersection and I came across this article:
https://math.stackexchange.com/questions/679622/intersection-between-conic-and-line-in-homogeneous-space/867428#...
2
votes
1answer
308 views
Fastest way to solve a sparse unsymmetric system many times
I have to solve a system $Ax^{(n)} = b^{(n)}$ many times, $A$ being a sparse (pentadiagonal in most part of its structure), unsymmetric, constant matrix.
Currently, I am performing the LU ...
1
vote
1answer
37 views
Householder QR for abstract vectors
Assume I have a sequence of vectors $v_k \in V$ in some abstract vector space $V$ not necessarily equal to $\mathbb{C}^n$. Can I still use the Householder QR decomposition in this case, even though ...
1
vote
0answers
113 views
Updating factorization of Laplacian (add/remove edges)
For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges.
...
0
votes
1answer
81 views
$LU$ Factorization of a nonsingular matrix with a particular pattern
Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$:
$$\begin{pmatrix}
1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\
0 & 1 &...
6
votes
2answers
262 views
Solving $A=B+AB$ without matrix inverse
I have a linear system of equations that can be expressed $$A=B+AB,$$ where $A$ and $B$ are real, symmetric matrices. I would like to solve for $A$ given $B$. At present, I solve for $A$ directly via $...
10
votes
1answer
224 views
The fast, and The Backward-Stable (left) $3\times 3$ matrix inverse
I need to compute a lot of $3\times3$ matrix inverses (for Newton iteration polar decomposition), with very small number of degenerate cases ($<0.1\%$).
Explicit inverse (via matrix minors divided ...
5
votes
1answer
342 views
Code to update dense QR and Cholesky factorizations
I am looking for some production-ready code to update dense QR and/or Cholesky factorizations (by adding / removing rows and columns or making small-rank updates -- yes, I need all these cases).
I ...
24
votes
10answers
6k views
Robust algorithm for $2 \times 2$ SVD
What is a simple algorithm for computing the SVD of $2 \times 2$ matrices?
Ideally, I'd like a numerically robust algorithm, but I'll like to see both simple and not-so-simple implementations. C code ...
