# 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.

988 questions
Filter by
Sorted by
Tagged with
886 views

### Which Sparse Matrix Solver Libraries can I run on Android?

The title says most of it. I'm looking for a lightweight and easy-to-use library that I can use for Android (NDK) projects. For dense stuff I like using Eigen but I haven't found many comprehensive (...
2k views

### precision vs matrix condition number

I have an application in which I am computing a quantity which is approximated by an average over $M$ points. In theory, the average converges to the correct quantity when $M$ is infinite. In practice,...
1k views

### Lanczos solver implementations in MATLAB/C++ give different results

I have transferred my MATLAB Lanczos solver for symmetric eigenvalue solvers to C++ with the help of Intel MKL and MTL4 libraries. I have some wrapper templates for MKL routines. However during the ...
2k views

### Schrodinger equation with periodic boundary conditions

I have a couple of questions regarding the following: I am trying to solve the Schrodinger equation in 1D using the crank nicolson discretization followed by inverting the resulting tridiagonal ...
297 views

1k views

### Krylov Subspace Methods for Dense Systems

I am currently researching on the viability of using KS methods for solving large dense systems. What I wish to prove (or disprove) is that methods like CG, BiCG and QMR are as good (if not better) ...
3k views

### What is a good stop criterion when using an iterative method to find eigenvalues?

I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors. What are good stop ...
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$...
195 views

### Looking for a mathematical proof of stability in floating point arithmetic of CG - any reference?

I am looking for a reference - paper, book, discussion, anything that has a mathematical proof for stability of the conjugate gradient method in floating point arithmetic. Something similar for ...
13k 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 ...
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 ...
94 views

### Applicability of combinatorial and support preconditioner

There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to ...
314 views

### Nested dissection on regular grid

When solving sparse linear systems using direct factorization methods, the ordering strategy used significantly impacts the fill-in factor of non-zero elements in the factors. One such ordering ...
726 views

### Is it possible to dynamically resize a sparse matrix in the Petsc library?

This may be a Petsc newbie question, but... I'm using Petsc to solve a large sparse linear system. The initial creation of the matrix is fairly slow, which I'm given to understand is largely due to ...
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?
130k 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 ...
505 views

### What should be the criteria for accepting/rejecting singular values?

I am solving a system using singular value decomposition. The singular values (before scaling) are: ...
202 views

### Is there one general approach to build a projection methods for different problems?

My question is probably going to be too general to answer it with a couple words. Could you please suggest a good reading in that case. Projection methods are used to reduce size of the solution space ...
362 views

### In what application cases are additive preconditioning schemes superior to multiplicative ones?

In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, ...
862 views

### Linear regression via SVD not producing best fit with escalating polynomial degree

I am using a basic singular value decomposition (via LAPACK) routine in FORTRAN to solve an overdetermined system in the form of $A\cdot X = B$ where $\mathrm{size}(A) = [m,n]$ with $m > n$. My ...
13k views

### Performance differences between ATLAS and MKL?

ATLAS is a free BLAS/LAPACK replacement that tunes itself to the machine when compiled. MKL is the commercial library shipped by Intel. Are these two libraries comparable when it comes to performance, ...
1k views

### How can I compute the Schur complement in PETSc?

How can I compute the Schur complement: $$S = K_{bb} - K_{ba} K_{aa}^{-1} K_{ab}$$ where $$K=\begin{pmatrix} K_{aa} & K_{ab} \\ K_{ba} & K_{bb} \end{pmatrix}$$ (in some ordering) is a ...
2k views

### Why is my parallel solver slower than my sequential solver?

I was playing around with PETSc and noticed that when I run my program with more than one process via MPI it seems to run even slower! How can I check to see what is going on?
1k views

### Efficient tridiagonal matrix algorithm implementation

I am solving a physical problem using implicit numerical scheme. This leads me to solving a linear equation with tridiagonal matrix. I've coded this algorithm from Wikipedia. I wonder if there is an ...
10k 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 ...