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.

104 questions
7k 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 (...
119k 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 ...
10k 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 ...
1k 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 ...
2k 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 ...
3k 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.
2k 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 ...
13k 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 ...
9k 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 ...
5k 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 ...
7k 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 ...
7k 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 ...
1k views

Estimation of condition numbers for very large matrices

Which approaches are used in practice for estimating the condition number of large sparse matrices?
2k 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 ...
392 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'...
29k 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) ...
3k 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 (...
15k 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 ...
20k 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 ...
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 ...
4k 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$...
6k 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 ...
657 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 ...
314 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 ...
2k 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 ...
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 ...
1k 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 ...
491 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 ...
819 views

405 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 ...
123 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 ...
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 ...
157 views

Support Vector Machines as Neural Nets?

This is more of a conceptual question. I have learned about Neural Nets, and I have some clue as to how Support Vector Machines work. I read somewhere however that given the appropriate kernel (is ...
2k 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 ...
229 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
939 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 ...
2k 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 ...
3k views

How to construct a prolongation and restriction operator for an algebraic multigrid solver?

I am trying to solve a linear system of equations that is sparse, but lacks any kind of banded structure. I have heard that there is a way to extend the principles of a multigrid solver for implicit ...
507 views

Large-scale generalized eigenvalue problem with low rank LHS matrix

Assume that we have generalized eigenvalue problem: $B^HB\textbf{x} = \lambda A\textbf{x}$ where $A$ is an nxn Hermitian sparse matrix (n is very large, so we do not have $A^{-1}$ but can solve ...
1k views

Performance optimization or tuning possible for Scalapack Gemm?

I'm comparing the performance of distributed gemm, using Scalapack over OpenBLAS, with threaded gemm, using OpenBLAS. It seems quite hard for me to get scalapack to give better results than ...
213 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 ...
1k views

Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
976 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)$ (...
446 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 ...