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

1,139 questions
Filter by
Sorted by
Tagged with
308 views

### Approximately "solving" a linear system of equations without a feasible solution

A linear system of equations has the form $Ax = b$, where a matrix $A$ and a vector $b$ are given, and I wish to find a solution vector $x$. Suppose that the system $Ax = b$ has no feasible solution. ...
• 311
943 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 (...
• 435
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,...
• 375
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 ...
• 143
348 views

• 3,620
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) ...
• 3,374
4k 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 ...
• 3,355
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
212 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 ...
• 41
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
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,929
115 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 ...
• 3,620
343 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 ...
• 4,480
895 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 ...
• 213
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?
140k 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.4k
866 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: ...
• 2,139
242 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 ...
• 501
417 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, ...
• 1,675
962 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 ...
• 2,139
16k 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, ...
• 1,599
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 ...
• 1,675
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?
• 1,370
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 ...
• 455
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
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,155