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.
132
questions
5
votes
0
answers
91
views
Determinant of matrix square root
I have a complex-symmetric matrix $A$ of size $n\times n$ with positive real part $\Re(A)>0$, and I need to calculate
$$\det\left(\sqrt{A}\right)$$
in the context of calculating a Gaussian integral....
- 203
4
votes
1
answer
144
views
Products of the Householder matrices during QR decomposition
It is often said that there is no need to form the Householder matrix during QR decomposition, however I fail to see how to "manage" the product of $n$ Householder matrixes and the matrix $A$...
- 327
3
votes
0
answers
88
views
Eliminate variables from a large system of equations
I have a large system of equations $Ax=0$. For context, the equations are invariants of some model. $A$ is sparse and typically has more columns than rows ($m < n$). The $x$ vector can be divided ...
- 31
1
vote
0
answers
62
views
SVD decomposition and the update problem of matrix differential equations
For a matrix $Y(t) \in \mathbb{R}^{m \times n}$, its rank-r approximation could be represented in a factorized SVD-like form.
$$
Y(t) = U(t) S(t) V^T(t),
$$
where $U^{T}U = I_m$, $V^{T}V = I_n$ and $S ...
- 141
0
votes
0
answers
83
views
Singular Matrix Error in Incomplete LU Decomposition
I’m currently working on solving the following PDE:
$$\begin{equation}
-(\mu_x \frac{\partial^2 u}{\partial x^2} + \mu_y \frac{\partial^2 u}{\partial y^2}) = f(x, y)\end{equation}$$
Where a right hand ...
- 43
1
vote
2
answers
107
views
Implementing matrix term version of Gauss-seidel
I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
- 265
1
vote
1
answer
100
views
enough conditions to check that a matrix doesn't have Cholesky factorization while factorizing it
I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab:
...
- 125
2
votes
0
answers
68
views
Efficient Algorithm for LU-Factorization of Modified Matrix with Last Column Alteration If We Have Its Not-Modified LU-Factorization
Suppose that we have a $n\times n$ matrix $A$. We have its LU-factorization as $A=LU$ (or $PA=LU$ that $P$ is a permutation matrix). Now assume we change the last column of matrix $A$ and denote the ...
- 125
0
votes
0
answers
237
views
Right blocked linear equation solver on Dense Algebra and Sparse Algebra
I have implemented 1D mesh parallel QR decomposition and LU decomposition,I would like to ask if a linear equation Ax=b,b is a large matrix and I need to shard b or Shard A,b at the same time. Is ...
4
votes
1
answer
365
views
How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix
I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
- 141
0
votes
1
answer
101
views
row and column based distributed LU factorization
The LU parallel computation theories I've seen are based on $M\times N$ mesh computations, is there a theory for one dimensional device mesh LU parallel decomposition?
For example, $A$ is a matrix. we ...
4
votes
2
answers
271
views
Reordering eigenvalues in Schur factorization - MATLAB ordschur and LAPACK dtrsen not producing the same results
Disclaimer: I previously posted this on SO, but though it would be more relevant for scicomp. The original post has been deleted.
I have been trying to recreate the functionality provided by MATLABs <...
- 41
1
vote
1
answer
144
views
Calculating camera calibration matrix with Scilab
I'm not entirely sure whether this question belongs here or in DSP but I think this is the proper site.
I'm following these videos (first video, second video) to calibrate a camera for photogrammetry ...
- 131
4
votes
1
answer
182
views
Is there a way to generate a matrix-free decomposition for a matrix-free operator?
Hypothetical question for some code that I'm writing. Suppose I have an matrix-free linear operator $A$, i.e. the only thing I know about it is the forward action $v \mapsto Av$. For simplicity, let's ...
- 141
4
votes
1
answer
191
views
The error propagation in calculating the inverse using a matrix decomposition
I have been trying to calculate the matrix inverse of some large matrix with entries ranging by orders of magnitude. I tried to use the matrix decomposition to simplify the computation, where a matrix
...
2
votes
0
answers
151
views
Is the Hessian of the strain energy of a hyperelastic material positive definite in general
Is the spatial second derivative of the strain energy of a hyperelastic material positive definite in general?
If this is not a general property of hyperelastic materials are there techniques for ...
- 327
2
votes
0
answers
134
views
Does exact diagonalization of a matrix allow for efficient computation of a Lanczos basis?
Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the ...
- 41
5
votes
1
answer
386
views
Block-Tridiagonal Matrices with tridiagonal blocks
The Setup
Using finite differences to discretize the 2d diffusion equation $$\partial_tu=\partial_x\left(A\partial_xu+B\partial_yu\right)+\partial_y\left(B\partial_xu+C\partial_yu\right)$$ we get a ...
- 153
2
votes
0
answers
36
views
How to exploit QR factorization implicitly
I meet a problem when I try to develop an iterative method for discrete inverse problem
$$Ax+e=b$$
where $A\in\mathbb{R}^{m\times n}$ and $e$ is a noise. I want to approximate the true solution $x_{...
- 21
1
vote
0
answers
131
views
What's the best modern algorithm for recursive least squares?
Recursive least squares can be implemented using the Sherman–Morrison formula to avoid resolving, however, have better methods without $n^2$ cost been developed? I'm interested if there is a good ...
- 111
1
vote
1
answer
74
views
Efficient and stable QR factorization of partially orthonormal matrix
Let $U \in \mathbb{C}^{m \times n_U}$ be an orthonormal matrix, let $A \in \mathbb{C}^{m \times n_A}$, and $m \geq n_U + n_A$. I want to compute a QR factorization $X = \left[U A\right] = QR$, with $Q ...
- 1,031
1
vote
1
answer
154
views
QR decomposition with only diagonal elements changing
I have to compute the QR decomposition of a matrix A repeatedly, each time with ONLY diagonal elements changing. Is there an efficient way to accomplish this ...
- 111
2
votes
0
answers
52
views
Finding spectrum of a Kronecker factored + block-partitioned matrix
I have dense $d\times d$ matrices $A$, $B$, $C$ with $d\approx 1000$ and want to find the top $10^5$ eigenvalues of the following positive definite matrix:
$$
\Sigma=
\left(\begin{matrix}
A\otimes A &...
- 2,735
0
votes
1
answer
93
views
Diagonalization of factored matrix
I have a matrix $X=CC^T$ that I want to diagonalize. Here $C$ is a known $n\times n$ matrix, which I could also factor as $LM$ if it helps, $L$ being a lower triangular matrix and $M$ another matrix. ...
- 436
1
vote
2
answers
535
views
Solution to Sylvester-like equation
I have an equation that is a bit similar to a Sylvester equation.
The equations is $AXB^T+X=E$, where all variables are matrices.
I could try to inverse $B$ and rewrite the equation as $AX+XB^{-T}=EB^{...
- 436
2
votes
0
answers
60
views
Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R?
Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB ...
- 767
4
votes
0
answers
105
views
Dense factorization specialized for RBF-FD method
In RBF-FD methods (see Fornberg & Flyer. A Primer on Radial Basis Functions with Application to the Geosciences. SIAM, 2015. Chapter 5.), the finite-difference stencil coefficients for a set of ...
- 637
1
vote
1
answer
111
views
Fast algorithm to compute chi-square
I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. ...
- 123
0
votes
2
answers
1k
views
Incomplete Cholesky factorization algorithm
I want to implement incomplete Cholesky factorization to precondition, the algorithm I refer from incomplete Cholesky factorization,
...
- 11
4
votes
1
answer
656
views
Incomplete Cholesky preconditioner for CG efficiency
I am currently solving the harmonic equation using a P1 FEM discretisation. The resulting matrix $A$ is SPD and fairly sparse so I use a preconditioned conjugate gradients (CG) solver to find a ...
- 2,352
1
vote
1
answer
1k
views
Givens rotation algorithm without matrix-matrix multiplication
I would like to implement a givenRotation algorithm without having matrix-matrix multiplication. Matrix-vector is fine or just for looping. I am to decompose a rectangular (m+1)xm Hessenberg matrix.
I ...
user41264
5
votes
2
answers
597
views
Computational method to compute both the (log) determinant and inverse of a matrix
Suppose I have a square matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ and a vector $\mathbf{b}\in\mathbb{R}^n$. In my application I need to accomplish two things.
I need to find the solution of the ...
- 183
6
votes
1
answer
268
views
Algorithm for solving systems which are nearly symmetric/adjoint?
I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations.
I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or ...
- 173
6
votes
1
answer
274
views
Solving Large Scale Sparse Linear System of Image Convolution
I want to invert a huge sparse (non-circulant) this below in a $Ax=y$ equation:
$$(\lambda I+ \beta D+ \sigma C)x=y$$
where
$I$ is an identity matrix, $D$ is a aiagonal matrix, $C$ is a circulant ...
- 61
1
vote
0
answers
61
views
Using the lower triangular portion of a matrix to return a Symmetric Positive Definite Matrix?
I've recently posted this question.
To summarise, I'm dealing with supposedly Symmetric Positive Definite(SPD) matrices, but due to machine-precision they end up not being SPD.
In a comment, a user ...
3
votes
2
answers
162
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 & ...
- 964
4
votes
2
answers
319
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 ...
- 183
8
votes
3
answers
1k
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 ...
- 183
1
vote
0
answers
74
views
Nonsymmetric permutations for LU factorisation of symmetric matrix
Let $A$ be a symmetric matrix. It is then well known that computing the LU factorisation of $PAP^T$ instead of $A$ for a suitably chosen permutation matrix $P$ can greatly reduce fill-in. My question ...
- 445
0
votes
1
answer
167
views
Solve for large array of PD matrices
I have N matrices that are positive definite, and I have to solve for a M vectors.
As M is large in my case, doing all solves simultaneously using np.linalg.solve ...
- 109
3
votes
1
answer
474
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 ...
user14831
2
votes
1
answer
246
views
Efficiently compute a projection matrix from Householders reflectors
Let $A \in \mathbb{R}^{m \times n}$ where $m \geq n$.
Let $B$ and $\tau$ be the result of applying LAPACK's dgeqrfp method (R on the upper right triangle, and the ...
1
vote
2
answers
155
views
Solving a specific sparse linear system without dense materialization
I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form
$$
\left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
- 113
2
votes
1
answer
444
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, ...
- 297
2
votes
0
answers
74
views
Does incomplete LU preconditioning improve the asymptotic scaling of Krylov subspace methods?
It is well known that unpreconditioned Krylov subspace methods applied to the finite-difference-discretised Poisson equation with $n$ grid points per direction require $O(n \, |\log(\varepsilon)|)$ ...
- 445
1
vote
1
answer
324
views
Range of a matrix from its complete orthogonal decomposition
In this StackOverflow answer, @Gokul has shown how to get a basis of the kernel of a matrix with the help of the 'Eigen' function CompleteOrthogonalDecomposition. ...
- 283
4
votes
0
answers
77
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}) = \...
- 41
2
votes
2
answers
538
views
"WY" representation of QR factorization -- implementations?
I have a matrix $A \in \mathbb{R}^{m \times n}$ where $m \gg n$ and I want to compute the full QR decomposition $A = QR$. Where $Q$ is an orthogonal $m \times m$ matrix.
Bishof & Van Loan (1987) ...
- 175
2
votes
1
answer
289
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 ...
- 33
2
votes
0
answers
430
views
Computing Singular Value Decomposition of small ($4\times 4$) matrices
I need to compute the Singular Value Decomposition (SVD) of many $4 \times 4$ matrices. I'm looking for SVD algorithms specialized for small matrices. I've read that the ...
- 131