We’re rewarding the question askers & reputations are being recalculated! Read more.

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.

Filter by
Sorted by
Tagged with
26
votes
10answers
7k 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 ...
13
votes
4answers
273 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, ...
9
votes
1answer
242 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 ...
7
votes
1answer
198 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 \...
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-...
6
votes
2answers
876 views

Computing smallest eigenvectors of a sparse matrix, having its inverse

I'm a bit confused by the vast amount of literature on solving eigenvalue problems. I have a sparse (large) matrix which I have already factored (by Cholesky or LDU). I would like to compute few ...
6
votes
2answers
1k views

Sparse Incomplete Cholesky

I'm looking for an efficient, multicore, library to do incomplete cholesky (possibly modified). Many ILU code exists, but I can't find much about IC except in PETSC or Pastix. Could some of you drop ...
5
votes
3answers
325 views

Does a symmetric positive definite matrix also have $\mathbf{A} = \mathbf{L}^T\mathbf{L}$ (where $\mathbf{L}$ is a lower triangular matrix)?

As we know, for a symmetric positive definite (SPD) matrix $\mathbf{A}$, there is a theorem about the Cholesky factorization $\mathbf{A}= \mathbf{L}\mathbf{L}^T$, where $\mathbf{L}$ is a lower ...
5
votes
2answers
278 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 $...
5
votes
2answers
349 views

Existence of incomplete cholesky factorization

What is the current state of research on the existence of incomplete cholesky factorizations (in the context of preconditioning) for symmetric positive definite matrices? I wonder in particular ...
5
votes
1answer
88 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 ...
5
votes
0answers
145 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?...
4
votes
1answer
126 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. (...
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 ...
4
votes
1answer
96 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,...
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 ...
4
votes
1answer
384 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 ...
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 ...
4
votes
1answer
34 views

Low rank update of QR of inverse

I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step: Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$ ...
4
votes
2answers
119 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: ...
4
votes
1answer
154 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
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. ...
3
votes
1answer
52 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-...
3
votes
1answer
319 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 ...
3
votes
1answer
249 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}}+[...
3
votes
1answer
83 views

Missing nonzeros in U matrix computed by SuperLU

On page 18 of SuperLU's user guide, the following sample input matrix A is given: ...
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 ...
3
votes
0answers
106 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 ...
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 ...
2
votes
1answer
346 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 ...
2
votes
1answer
779 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 (<...
2
votes
1answer
74 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 ...
2
votes
1answer
137 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 ...
2
votes
1answer
133 views

Converting matrices L and U output by dgssv() of SuperLU to triples format

How can I convert matrices L and U output by dgssvx() of SuperLU to triples format (to ...
2
votes
1answer
56 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-...
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|\...
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 ...
2
votes
0answers
440 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 ...
1
vote
1answer
457 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
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
125 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
135 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?
1
vote
1answer
59 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 ...
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
18k views

why Lapack routine dgesv doesn't solve this?

Suppose I have the following 3 by 3 matrix: p<-3 X<-matrix(1/p,p,p) --$\pmb X$ is just a $p$ by $p$ matrix where every entry is $1/p$. Now I want to solve ...
1
vote
1answer
44 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
47 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
452 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 ...
1
vote
1answer
183 views

Non-negative matrix factorization for sparse input

Looking for some software to deal with 50kx50k sparse matrix applying non-negative matrix factorization. Do you know any?
1
vote
1answer
40 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 ...