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
28
votes
11answers
8k 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
380 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, ...
10
votes
1answer
394 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 ...
8
votes
3answers
444 views

Accurate Way to Calculate Matrix Powers and Matrix Exponential for Sparse Positive Semidefinite Matrices

I do need to numerically calculate the following forms for any $x\in\mathbb{R}^n$, possibly in python: $x^T M^k x$, where $M\in\mathbb{R^{n\times n}}$ is a PSD sparse matrix, $n$ can be quite large ...
7
votes
3answers
409 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 ...
7
votes
1answer
277 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
264 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
916 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
2k 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
2answers
319 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
1answer
163 views

Algorithm to factorize matrix whose many rows are already of upper triangular form?

I have a matrix whose many rows are already in the upper triangular form. $$\begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{5} \\ 0 & x_{22} & x_{23} & x_{...
5
votes
2answers
207 views

Block-matrix: optimal fill-in reduction for LU factorization

Consider a square $N \times N$ block-matrix $\mathbf{A}$, where each $n \times n$ block $\mathbf{A}_{ii}$ is either a dense block or a zero-block. So, $N$ denotes the number of blocks, $n$ denotes the ...
5
votes
1answer
92 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
65 views

Why the two Gram-Schmidt algorithms produce different results for qr factorization?

For the qr factorization using classic Gram-Schmidt algorithm, I found the 2 different implementations below. The first one uses the for loop to compute the upper ...
5
votes
0answers
181 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
2answers
129 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 ...
4
votes
1answer
591 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
139 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
132 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
122 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
2answers
386 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 ...
4
votes
1answer
505 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
140 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
140 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
242 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
163 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-...
4
votes
0answers
54 views

Efficient computation of marginalized multivariate normal likelihood

In general,if we know that the marginal Gaussian distribution for some variable $\textbf{x}$ and a conditional Gaussian distribution for some $\textbf{y}|\textbf{x}$ of the forms: $$p(\textbf{x}) = \...
3
votes
2answers
98 views

Efficient schemes for solving the extended Saddle point problem

I am interested in knowing some efficient techniques for solving the following extended Saddle point problem. \begin{align} \begin{bmatrix} A & B^T & C^T \\ B & 0 & 0 \\ C & ...
3
votes
1answer
716 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 ...
3
votes
1answer
323 views

Why is 'scipy.sparse.linalg.spilu' less efficient than 'scipy.linalg.lu' for sparse matrix?

I have a matrix B which is sparse and try to utilize a function scipy.sparse.linalg.spilu specialized for sparse matrix to ...
3
votes
2answers
179 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
122 views

Quick way to find a common basis of eigenvectors between 2 matrices : valid or not?

Following the advise of @Federico Polonion a previous post, one suggested, to find a basis of common eigen vectors between 2 matrices, to simply do : Generate 2 ...
3
votes
1answer
120 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
575 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
265 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
87 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
1answer
396 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-...
3
votes
0answers
71 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
161 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
40 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 ...
3
votes
0answers
561 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 ...
3
votes
0answers
136 views

What is the computational cost of using complex numbers in contrast to real numbers in matrix operations, e.g. $LU$ or $LDL^T$ factorizations? [duplicate]

I am curious about how much one loses in terms of computational cost when complex numbers are used instead of real numbers? I guess the number of floating-point operations and memory doubles, but I ...
2
votes
1answer
75 views

Functions from Scipy, Blas, or Lapack that compute only upper triangular matrix

My goal is to transform a matrix into upper triangular form in Python. I know the function scipy.linalg.lu will do LU decomposition and get both upper and lower ...
2
votes
1answer
106 views

Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular

I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
2
votes
1answer
607 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 ...
2
votes
1answer
455 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
23k 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 ...
2
votes
1answer
116 views

Methods to improve the efficiency and the memory requirement of LU factorization for complex symmetric system matrix

I want to solve a linear set of equations (Ax=b) using LU decomposition. My "A" matrix is a complex matrix which is ...
2
votes
1answer
151 views

Bareiss algorithm vs. LU-decomposition

I at the moment try to fully understand the Bareiss algorithm for calculating determinants. One question that came to my mind is the following: Why is LU-decomposition much more often used than the ...
2
votes
1answer
172 views

Reference for QR algorithm for complex matrix

I am trying to find out if the known QR algorithm to find the eigenvalues of a real matrix, which can be found in the book Fundamentals of Matrix Computations, can also be used for complex matrices ...