13 votes
Accepted

When do not use preconditioners for sparse linear system of equations?

In my experience, you always need (or better use) some form of preconditioning. The type and complexity of the precondition would vary depending on the task though. From Y. Saad, Iterative Methods for ...
user avatar
  • 8,382
12 votes
Accepted

Without positive definiteness, does an iterative solver work?

No, positive definiteness (and symmetry) are only precondition to using the Conjugate Gradient method. But there are plenty of other iterative methods such as MinRes and GMRES that can be used for ...
user avatar
8 votes
Accepted

Using matrix exponential to solve linear system

You are effectively asking how to compute $y=(\log M )^{-1}b$, where $M=e^A$ is the given matrix. There are several methods for computing $f(M)b$ without forming $f(M)$, and they are reviewed here. ...
user avatar
7 votes
Accepted

What is the **contraction factor and convergence factor** of a iteration method?

These concepts are related. Let $A = M - N$ and consider the iteration $$ M x_{k+1} = N x_k + b. $$ We can write this as a mapping $\Phi : \mathbb{R}^n \to \mathbb{R}^n$ defined by $$ \Phi(y) = M^{-1}(...
user avatar
  • 611
7 votes
Accepted

Why do not we choose the error solution norm as an iterative method's criterion?

We can't use the criterion you show last in practice because it requires us to know what $\kappa(A)$ is. But computing the condition number is, in general, more expensive than solving a linear system. ...
user avatar
7 votes

Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB

As Federico has mentioned, you probably don't want to deprive yourself of the learning experience. I'll just give you a small nudge in the right direction. You will never be able to store $A$. You ...
user avatar
  • 1,189
6 votes
Accepted

Fastest way to solve a sparse unsymmetric system many times

Generally speaking, for many right-hand side (RHS) problems, a direct solver is a more feasible solution for several reasons: Major computations are performed during the factorization step (which is ...
user avatar
  • 8,382
6 votes
Accepted

Is steady linear elasticity inherently ill-conditioned?

The condition number for the stiffness matrix of any method (finite elements, finite volumes, finite differences) applied to a second order differential operator always grows as ${\cal O}(h^{-2})$ ...
user avatar
6 votes
Accepted

Solving for a vector in a linear system that is both left and right multiplied

Your second term is linear in $x$, so it can be rewritten as $Cx$ where $C$ is a suitable $n\times n$ matrix. You just need to figure out what its entries $C_{ij}$ are: for this you need a little ...
user avatar
6 votes

Solving for a vector in a linear system that is both left and right multiplied

Based on Federico's answer, I think you can easily figure out what are $C_{ij}$ entries by explicitly writing the second term ($Bxv$) as: $$(Bx)_{ij} = \sum_{\alpha=1}^{n} B_{ij\alpha} x_{\alpha}$$ $...
user avatar
6 votes
Accepted

Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular

It's a complicated question, which is why I've recorded a whole bunch of video lectures on the topic :-) Take a look at lectures 34 and following here: https://www.math.colostate.edu/~bangerth/videos....
user avatar
5 votes
Accepted

How to verify solution to pre-conditioned linear systems solver?

You've started with a singular linear system of equations $Ax=b$. As a practical matter, it's unlikely that $b$ lies exactly in the range of $A$, so at best you can find a least squares solution that ...
user avatar
5 votes
Accepted

How "sparse" should a sparse matrix be to see benefits?

This kind of scaling is fairly common and sparse direct factorization methods are commonly used on matrices of up to a few hundred thousand rows and columns. By the time you get to $N=20$, you’ll ...
user avatar
5 votes
Accepted

Why Krylov subspace iterative methods are faster than classical iteration?

I must admit I never actually checked all the details myself, but I think that's a sketch of the general idea. The $k$th iterate $x_k$ produced by Richardson iteration lies in the Krylov subspace $...
user avatar
5 votes
Accepted

How to implement flexible gmres in matlab?

First of all, MATLAB's gmres assumes that the preconditioner you use is linear. This is important! Actually it is the main difference between FGMRES and GMRES. ...
user avatar
4 votes

Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights

Michael Saunders wrote a sparse LU package that can do rank-1 updates, LUSOL. You could try to use that, since you write that direct solvers are viable for your problem.
user avatar
4 votes

Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights

It appears to me that you are dealing with a sequence of linear systems $A_j x_j = b$, where $A_{j+1}$ is a low rank modification of $A_{j}$. In your case, I would investigate if the Krylov subspace $...
user avatar
4 votes
Accepted

Least-squares for a diagonal matrix

The closed-form solution is available by projecting the problem into the space spanned by B. To see this, note that we have $$\min_{v\in\mathbb{R}^{n}}\|X-BD_{v}B^{T}\|_{F},$$ but if we introduce $\...
user avatar
4 votes

How to obtain linear tridiagonal system from PDE

Welcome to the site. You are actually virtually finished, but may not have realised it yet. A tridiagonal linear system is another name for a matrix problem which only has non zero entries on the ...
user avatar
  • 2,199
4 votes
Accepted

Solving an m x m symmetric linear system involving a matrix multiplication versus an (n+m) x (n+m) system

In my opinion, you need a really good excuse to take a symmetric positive definite system and then turn it into an indefinite system. The first thing I would try is the conjugate gradient method ...
user avatar
  • 576
4 votes
Accepted

1D FEM for nonlinear diffusion coefficient

You would need to linearize the problem. I prefer to do it before discretization but it's possible to do also after discretization. (I'm a bit skeptical of linearization after discretization because I ...
user avatar
  • 1,877
4 votes

Algebraic multigrid as solver and as preconditioner

Most people use (algebraic as well as geometric) multigrid as preconditioners these days. It's an empirical observation that that leads to faster convergence in terms of iterations, given that in a ...
user avatar
4 votes

Simplest solver for linear equation systems

I'd recommend a BLAS1/2-style implementation of LU decomposition with partial pivoting, along with forward/backward triangular solves. If you only have single digit numbers of unknowns, it should be ...
user avatar
  • 4,316
3 votes
Accepted

What are the names of the variables in the linear system $Ax=b$

$A$ is a discretized version of your differential operator + enforced boundary conditions. The names for $A$ can vary depending on the way the PDE is being discretized. For example, in FEM, it will be ...
user avatar
  • 8,382
3 votes

Solve a very large linear system (question about a library linear algebra to do this)

LSQR uses only 4 N-vectors of MEMORY. It might be your choice if storage must be minimized. It is fairly good otherwise, too, but probably not the best one (unless your matrix is non-square; then the ...
user avatar
  • 161
3 votes

Solve a very large linear system (question about a library linear algebra to do this)

Since the matrix is considerably sparse and well-conditioned (if it is true), I suggest you can try to use Krylov subspace method, which can only use the information of matrix-vector product; such as ...
user avatar
3 votes

Solving a system of linear equations with only an approximate solution

It seems you are looking for an optimization (here, specifically a fit). You have some experimental data and you want to have a simple model explaining it. The simplest way is using the Ordinary ...
user avatar
3 votes
Accepted

Solve rank one update to LU using plain vanilla LU routine

The eta factorization of the basis is a technique widely used in the simplex method for LP to handle rank one column updates. The same idea can be modified to handle rank one row updates, I'll ...
user avatar
3 votes
Accepted

MATLAB: Matrix whose elements depend on its indicies

A simple approach: ...
user avatar
3 votes
Accepted

Solving "Hadamard systems"

Ultimately, it depends on the sparsity of $A$ and $B$ and the symmetry of the resulting hadamard product. The hadamard product will aggregate the sparsity structure of $A$ and $B$. So if one or the ...
user avatar
  • 11.8k

Only top scored, non community-wiki answers of a minimum length are eligible