Questions tagged [matrix-factorization]
Decomposition of a matrix into a product of matrices with special properties. Common matrix factorizations include LU, QR, SVD, and Cholesky.
62
questions
4
votes
1answer
76 views
Do most statistical packages and libraries in high-level programming languages rely on LAPACK for their matrix inversion operations?
Possible an open-ended question, but I am wondering if most statistical packages and libraries, for instance, Stata, R, Python's NumPy and MATLAB rely on LAPACK algorithms to perform matrix operations,...
1
vote
1answer
51 views
How to avoid unnecessary checks when inverting this LU decomposition
Background for the question
I am currently working on a Matlab code in which the systems of linear equations $Ax_1 = b_1$, $Ax_2 = b_2$, ... have to be solved. As the matrix $A$ is constant during ...
3
votes
1answer
50 views
Weighted QR Implementation
Say I want a QR decomposition of matrix $A$, where orthogonality of $Q$ is with respect to a generic non-degenerate positive-definite bilinear form $\phi$ (in my case, $\phi$ is "defined" by a finite-...
1
vote
1answer
115 views
Cholesky for ill-conditioned/singular covariance matrices
Can someone suggest a way to get Cholesky factorization of a singular covariance matrix? I need it to match Cholesky on full-rank matrices, ie coordinate order should be preserved. My attempt below ...
1
vote
1answer
41 views
Incomplete LU decomposition of sparse matrix
I have a sparse matrix stored in CSR format. For this matrix, I would like to get the incomplete LU decomposition. I tried to find algorithms which can utilize the CSR format but I could not find ...
1
vote
1answer
41 views
How to use QZ decomposition for single matrix in Matlab?
Can I use QZ decomposition on a single square matrix in Matlab?
Like,
[Aa,Q,Z]=qz(A);
1
vote
1answer
57 views
Classical vs. modified Gram-Schmidt
It is often said that modified Gram-Schmidt is more robust with respect to rounding errors than classical Gram-Schmidt, but it is very hard to find a good explanation / example of why this is so. Can ...
2
votes
1answer
54 views
Givens rotation vs 2x2 Householder reflection
The usual story of Givens rotations vs Householder reflections is that Householder reflections are better if you want to map a long vector to $e_1$, while Givens is better if you want to map a 2-...
1
vote
1answer
51 views
Software for parallel incomplete LU factorisation
I am looking for a software package to compute incomplete LU factorisations in parallel. Further considerations are:
The package must allow for arbitrary level-of-fill or threshold-based truncation. ...
2
votes
0answers
68 views
Regularized least squares with QR factorization
Consider the regularized least squares problem
$$
\min_x || b - A x ||^2 + \lambda^2 ||x||^2
$$
which is equivalent to
$$
\min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
4
votes
2answers
113 views
Inverting a matrix from LU decomposition
The LAPACK routines xGETRI compute the inverse of a matrix $A = PLU$ in its LU decomposed form by first computing $U^{-1}$, and then solving the system:
$$
(A^{-1} P) L = U^{-1}
$$
My question is: ...
2
votes
1answer
72 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 ...
1
vote
1answer
70 views
Pivoted Cholesky vs Modified Cholesky
I am solving nonlinear least squares problems with the normal equations approach, so on each iteration, I need to solve:
$$
J^T J \delta = -J^T f
$$
for the step $\delta$, where $J$ is a large (...
2
votes
0answers
29 views
ILUTP in sparse.linalg.spilu?
In Matlab, an ILU with threshold and pivoting (ILUTP) can be passed by default as:
setup.type = 'ilutp';
[L, U] = ilu(A, setup);
Looking for an equivalent in ...
3
votes
0answers
63 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
118 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
103 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
94 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 ...
3
votes
2answers
125 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.
...
4
votes
2answers
101 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
36 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
419 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
251 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
193 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
128 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
61 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
94 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
132 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?
13
votes
4answers
266 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
164 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
343 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
2answers
171 views
numerically stable routines to compute $M = B A^{-1} B$
Rather than
gesv -> solve $AX = B$
gemm -> compute $M = BX$,
somehow I feel there are better ways to compute $M$ with lapack/mkl?
1
vote
1answer
39 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
119 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.
...
5
votes
0answers
142 views
Rank-one Update to a Rank Revealing QR (RRQR) Factorization?
Suppose we are given an RRQR factorization for some matrix $A \in \mathbb{R}^{m \times n}$, $A\Pi = QR$ where $m > n$.
Is there a cheap way to update $A' = A + uv^{\top}$ given this factorization?...
0
votes
1answer
84 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 &...
5
votes
2answers
275 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 $...
9
votes
1answer
238 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 ...
1
vote
1answer
435 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 ...
4
votes
1answer
372 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 ...
3
votes
1answer
298 views
Solve rank one update to LU using plain vanilla LU routine
I have a large number of systems of the form:
$$A_ix=b,$$
where each $A_i,i>0$ is a rank one update of $A_{i-1}$ and the $A_i$ are dense matrices.
I was wondering whether it is possible to use the ...
4
votes
1answer
97 views
Does $\log(\det(A))$ equals sum of log of diagonal elements of D in LDLT decomposition?
For a large matrix $A$, I need to evaluate the $\log(\det(A))$. I already have it's LDLT decomposition.
Is it possible to evaluate the $\log\det$ with the elements of the diagonal $D$ of the LDLT ...
3
votes
1answer
230 views
Symmetric nonnegative matrix factorization
Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving
$$
\begin{array}{rl}
\min_U & \sum_{ij} \left(A_{ij}\ln\frac{A_{ij}}{[UU^\top]_{ij}}+[...
1
vote
1answer
69 views
Big errors while calculating Complex Cholesky Factorization
I am using my own Routine to calculate the Cholesky-Factorization of a complex, positive definite symmetric Matrix.
My Code Looks like this:
...
2
votes
0answers
427 views
Difference between fast and normal Givens Rotations?
would someone be so kind as to explain me the difference between the ordinary givens-rotation and the fast givens-rotation?
I know that the fast givens Rotation reduces the Count of operations to ...
4
votes
1answer
86 views
Is there an efficient $O(n^2)$ way to get the eigen decomposition given a LDL factorization?
Let's say I have a LDL factorization of a matrix A.
Is there an efficient $O(n^2)$ way to get the eigen decomposition of A given it's LDL factorization?
Is there a more efficient way, in case L and ...
2
votes
1answer
768 views
Solve Ax=B where B is a matrix in parallell
I try to solve the problem $Ax=B$ where $A$ is a large sparse $n\times n$ matrix, and $B$ is a dense $n\times m$ matrix (here $n=754850$ and $m=182$). The backslash operator yields correct solution (<...
1
vote
1answer
90 views
What is the cost of factorization for one-dimensional sparse problems?
In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that:
With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ fill-...
1
vote
1answer
55 views
Is there an upper bound for fill-ins for indefinite triangular factorization?
For $A=LU$, or $A=LDL^T$ factorization, bandwidth is preserved when there is no pivoting. This is true even for indefinite A, see question. However, when there is pivoting band structure is destroyed, ...
5
votes
1answer
86 views
Is the bandwidth of indefinite A equal to its factor L in LDL^T?
In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
