Questions tagged [linear-algebra]
Questions on the algorithmic/computational aspects of linear algebra, including the solution of linear systems, least squares problems, eigenproblems, and other such matters.
138
questions
58
votes
4
answers
9k
views
What guidelines should I follow when choosing a sparse linear system solver?
Sparse linear systems turn up with increasing frequency in applications. One has a lot of routines to choose from for solving these systems. At the highest level, there is a watershed between direct (...
- 3,145
170
votes
8
answers
139k
views
Recommendations for a usable, fast C++ matrix library?
Does anyone have recommendations on a usable, fast C++ matrix library?
What I mean by usable is the following:
Matrix objects have an intuitive interface (ex.: I can use rows and columns while ...
- 30.3k
30
votes
2
answers
15k
views
Why is my iterative linear solver not converging?
What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...
- 25.6k
10
votes
1
answer
4k
views
full rank update to cholesky decomposition
Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate
$det(A)$
$A^{-1}X$ for some ...
- 375
18
votes
6
answers
2k
views
How to reorder variables to produce a banded matrix of minimum bandwidth?
I'm trying to solve a 2D Poisson equation by finite differences. In the process, I obtain a sparse matrix with only $5$ variables in each equation. For example, if the variables were $U$, then the ...
- 12k
16
votes
1
answer
5k
views
How can I estimate the condition number of a large sparse matrix using PETSc?
I have a PETSc Mat and would like to estimate its condition number.
- 25.6k
23
votes
3
answers
3k
views
Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?
Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?
For example, if each $D_i$ is ...
- 3,909
40
votes
3
answers
18k
views
How to choose a method for solving linear equations
To my knowledge, there are 4 ways to solving a system of linear equations (correct me if there are more):
If the system matrix is a full-rank square matrix, you can use Cramer’s Rule;
Compute the ...
- 647
28
votes
3
answers
4k
views
What is the principle behind the convergence of Krylov subspace methods for solving linear systems of equations?
As I understand it, there are two major categories of iterative methods for solving linear systems of equations:
Stationary Methods (Jacobi, Gauss-Seidel, SOR, Multigrid)
Krylov Subspace methods (...
- 12k
18
votes
4
answers
4k
views
Why can't Householder reflections diagonalize a matrix?
When computing the QR factorization in practice, one uses Householder reflections to zero out the lower portion of a matrix. I know that for computing eigenvalues of symmetric matrices, the best you ...
- 4,480
16
votes
2
answers
2k
views
Estimation of condition numbers for very large matrices
Which approaches are used in practice for estimating the condition number of large sparse matrices?
- 3,196
40
votes
4
answers
35k
views
How does the MATLAB backslash operator solve $Ax=b$ for square matrices?
I was comparing a few of my codes to "stock" MATLAB codes. I am surprised at the results.
I ran a sample code (Sparse Matrix)
...
- 3,344
25
votes
2
answers
11k
views
Libraries for solving sparse linear systems
There are a number of different libraries out there that solve a sparse linear system of equations, however I'm finding it difficult to figure out what the differences are.
As far as I can tell there ...
- 1,155
20
votes
3
answers
11k
views
Null-space of a rectangular dense matrix
Given a dense matrix $$A \in R^{m \times n}, m >> n; max(m) \approx 100000 $$ what is the best way to find its null-space basis within some tolerance $\epsilon$?
Based on that basis can I then ...
- 1,111
14
votes
3
answers
10k
views
Understanding how Numpy does SVD
I have been using different methods to calculate both the rank of a matrix and the solution of a matrix system of equations. I came across the function linalg.svd. Comparing this to my own effort of ...
- 529
11
votes
1
answer
8k
views
Are there any heuristics for optimizing the successive over-relaxation (SOR) method?
As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
- 12k
9
votes
2
answers
637
views
Eigenvectors of a small norm adjustment
I have a dataset that is slowly changing, and I need to keep track of eigenvectors/eigenvalues of its covariance matrix.
I've been using scipy.linalg.eigh, but it'...
- 2,273
5
votes
1
answer
1k
views
Fast algorithm for computing cofactor matrix
I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
- 53
34
votes
6
answers
33k
views
What is the fastest way to calculate the largest eigenvalue of a general matrix?
EDIT: I am testing if any eigenvalues have a magnitude of one or greater.
I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix.
I have been using R's ...
- 511
30
votes
11
answers
10k
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 ...
- 966
29
votes
4
answers
19k
views
Dealing with the inverse of a positive definite symmetric (covariance) matrix?
In statistics and its various applications, we often calculate the covariance matrix, which is positive definite (in the cases considered) and symmetric, for various uses. Sometimes, we need the ...
21
votes
1
answer
3k
views
Diagonal update of a symmetric positive definite matrix
$A$ is a $n \times n$ symmetric positive definite (SPD) sparse matrix. $G$ is a sparse diagonal matrix. $n$ is large ($n$ >10000) and the number of nonzeros in the $G$ is usually 100 ~ 1000.
$A$ has ...
luogyong
17
votes
2
answers
5k
views
Stopping criteria for iterative linear solvers applied to nearly singular systems
Consider $Ax=b$ with $A$ nearly singular which means there is an eigenvalue $\lambda_0$ of $A$ that is very small. The usual stop criterion of an iterative method is based on the residual $r_n:=b-Ax_n$...
- 1,319
16
votes
3
answers
2k
views
multigrid method to solve PDE
I need simple explanation of the Multigrid Method or some literature about this.
I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with ...
- 373
12
votes
3
answers
2k
views
Numerically stable explicit solution of small linear system
I have an inhomogeneous linear system
$$
Ax=b
$$
where $A$ is a real $n\times n$ matrix with $n\leq 4$. The nullspace of $A$ is guaranteed to be of zero dimension so the equation has a unique ...
- 1,119
12
votes
1
answer
1k
views
Smallest eigenvalue without inverse
Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly.
Is there an iterative algorithm for finding the ...
- 1,341
11
votes
3
answers
2k
views
What's the current state of the art regarding algorithms for the singular value decomposition?
I'm working on a header-only matrix library to provide some reasonable degree of linear algebra capability in as simple a package as possible, and I'm trying to survey what the current state of the ...
- 211
10
votes
2
answers
609
views
Which novel data structures are used in adaptive FEM?
A lot of adaptive FEM libraries use more advanced mesh data structures to handle adding/removing nodes, edges, triangles, tetrahedra, etc. For example, the p4est library uses octree data structures ...
- 10.1k
9
votes
2
answers
737
views
Applying matrix square root inverse in matrix-free regime
Let $A$ be a large symmetric positive definite matrix, and suppose that we can efficiently apply $A$ and have a fast solver to apply $A^{-1}$, but we do not have access to the matrix entries for ...
- 3,143
9
votes
3
answers
1k
views
Iterative methods for indefinite systems without block structure
Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form
$$\begin{pmatrix} A & B^t \...
- 3,590
6
votes
2
answers
444
views
What guidelines should I use when choosing a scalable linear solver?
There are many different linear solvers, some which work best for diagonally dominant matrices, some for symmetric, some for positive definite ones, some for banded matrices, etc... There are direct ...
- 12k
6
votes
3
answers
5k
views
How to find QR decomposition of a rectangular matrix in overdetermined linear system solution?
While trying to find cell-centered gradients in finite volume method computation of incompressible fluid flow I get over-determined linear system. This is a well known "cell based least-square" ...
- 1,403
5
votes
2
answers
1k
views
Perturbation of Cholesky decomposition for matrix inversion
I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$
where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...
5
votes
2
answers
574
views
How to parallelize a banded direct solver?
I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian ...
- 12k
4
votes
1
answer
1k
views
LU Decomposition of PSD Matrix + Diagonal Matrix
If I have a psd, symmetric matrix $\mathbf{A}$ and I need to do LU decomps on $\mathbf{B_i}= \mathbf{A} + \mathbf{D_i}$ (where $\mathbf{D_i}$ is a diagonal psd matrix, where $\mathbf{D_i}$ changes ...
- 41
3
votes
1
answer
452
views
How many operations are needed for LAPACK's zgesv to solve a linear system?
I have a linear system of complex numbers. I am using LAPACK' zgesv (actually I am using intel MKL LAPACKE, but I am assuming the algorithm is the same). No assumption can be made about the system.
I ...
2
votes
1
answer
1k
views
Doubt regarding stopping criterion for Newton method
I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
- 666
1
vote
1
answer
480
views
Calculate inverse of dense matrix with entries of very different magnitude
I need to calculate the inverse of a dense matrix, with some elements taking values as high as 1e9 and some around 1e2. What would be the best method to do it?
Note:
I am more concerned about the ...
- 113
18
votes
3
answers
10k
views
Efficient computation of the matrix square root inverse
A common problem in statistics is computing the square root inverse of a symmetric positive definite matrix. What would be the most efficient way of computing this?
I came across some literature (...
- 345
17
votes
1
answer
2k
views
Can a Krylov subspace method be used as a smoother for multigrid?
As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
- 12k
16
votes
3
answers
16k
views
What is the fastest way to compute all eigenvalues of a very big and sparse adjacency matrix in python?
I'm trying to figure out if there is a faster way to compute all the eigenvalues and eigenvectors of a very big and sparse adjacency matrix than using scipy.sparse.linalg.eigsh As far as I know, this ...
- 263
15
votes
2
answers
573
views
Is there any way to do "double preconditioning"
Question:
Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$:
$$A \approx B^TB$$
and
$$A \approx C^TC,$$
where the inverses of the factors $B, ...
- 3,143
14
votes
6
answers
1k
views
Approximate spectrum of a large matrix
I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard.
I am willing to settle for an approximation. Are there approximation ...
- 3,068
13
votes
0
answers
707
views
Fast Eigenvalue and SVD Solver for Structured Matrices
I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to ...
- 241
12
votes
3
answers
3k
views
Sparse linear solver for many right-hand sides
I need to solve the same sparse linear system (300x300 to 1000x1000) with many right hand sides (300 to 1000).
In addition to this first problem, I would also like to solve different systems, but with ...
- 353
12
votes
2
answers
3k
views
How is the SVD of a matrix computed in practice
How does MATLAB, for instance, calculate the SVD of a given matrix? I assume the answer probably involves computing the eigenvectors and eigenvalues of A*A'. If ...
- 589
12
votes
4
answers
3k
views
Finding the square root of a Laplacian matrix
Suppose the following matrix $A$ is given
$$ \left[\begin{array}{ccc}
0.500 & -0.333 & -0.167\\
-0.500 & 0.667 & -0.167\\
-0.500 & -0.333 & 0.833\end{array}\right]$$
with ...
- 1,663
12
votes
1
answer
285
views
Algorithms for linear system of ODEs
I wonder: what is the best algorithm to solve
\begin{equation}
\frac{du}{dt} = Au
\end{equation}
Where $A$ is a real $n\times n$ matrix. A is not explicitly time-dependent, usually sparse but not ...
- 390
12
votes
1
answer
742
views
Inverse problem in linear ODE
I have a linear ordinary differential equation (ODE) with a system matrix with constant coefficients: $$\dot{y}(t) = \mathcal{A}\; y(t), \quad y(0) = y_0$$ with $y(t) \in \mathbb{R}^{n \times 1}$ and $...
- 6,169
11
votes
2
answers
1k
views
Which iterative linear solvers converge for positive semidefinite matrices?
I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$
(...
- 589