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
2
votes
0answers
61 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
99 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
65 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
59 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
1answer
128 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
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
2answers
100 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

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
99 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
89 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
120 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. ...
6
votes
2answers
248 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-...
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
315 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 ...
7
votes
1answer
180 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 \...
13
votes
4answers
256 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, ...
5
votes
0answers
128 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?...
9
votes
1answer
226 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 ...
24
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 ...
2
votes
1answer
109 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
1answer
179 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
0answers
59 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
88 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
127 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?
3
votes
1answer
227 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
153 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
328 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
170 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
118 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
82 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
265 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 $...
1
vote
1answer
400 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 ...
3
votes
1answer
264 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
353 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 ...
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: ...
4
votes
1answer
91 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 ...
2
votes
0answers
407 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
81 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
745 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 (<...
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 ...
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 ...
-5
votes
1answer
196 views

Can anyone give me some suggestions about optimize my Matlab codes?

recently, I try to write a Matlab codes to implement a sparse approximation inverse factorization method proposed by M. Benzi in his paper http://www.mathcs.emory.edu/~benzi/Web_papers/ainv.pdf this ...
1
vote
1answer
117 views

Compiling HSL_ME57 and interfacing with C code

Has anyone here had any success (or at least tried) compiling the HSL_ME57 (or similar such as MA57, etc.) matrix factorization libraries? Do any C wrappers exist for the Fortran function calls? I'm ...
1
vote
0answers
115 views

Efficient way to do congruent transformation using matrix inverse?

I know a square self-adjoint matrix $S_{vv}$ and I want to find: $S_{rr} = HS_{vv}H^{\dagger}$ where $\dagger$ denotes conjugate transpose. I do not know $H$ but I do know $H^{-1}$. What is the ...
1
vote
1answer
17k 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 ...
4
votes
1answer
153 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-...