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 ...
- 8,602
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 ...
- 54.1k
9
votes
Is it really necessary to solve a system of linear equations in the Finite Element Method?
I think your question is actually pretty fundamental and deserves a thoughtful answer.
Paraphrasing a bit, your question is perhaps motivated by the observation that engineering design is often ...
- 4,822
8
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}(...
- 791
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. ...
- 1,081
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. ...
- 54.1k
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 ...
- 1,386
7
votes
Correctness of direct numerical solution of ill-conditioned linear system
One thing you can do to test it is computing the residual $b - A \tilde{x}$ in higher precision. If the residual is small (and this will always happen with an accurate solution), then you can testify ...
- 11.1k
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 ...
- 8,602
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})$ ...
- 54.1k
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 ...
- 11.1k
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}$$
$...
- 2,332
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....
- 54.1k
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 ...
- 18.5k
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 ...
- 18.5k
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 $...
- 11.1k
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. ...
- 2,411
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.
- 11.1k
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 $...
- 1,391
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 ...
- 2,229
4
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 ...
- 18.5k
4
votes
Why OpenFOAM uses its own data structures and linear solvers?
In the light of more recent information:
OpenFOAM follows the C++11 standard without any exception at the time of writing. Therefore, you can use any C++ containers of this standard within OpenFOAM.
...
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 ...
- 661
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 ...
- 2,041
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 ...
- 54.1k
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 ...
- 4,822
4
votes
Interpolation and Restriction operators in Multigrid
It's fundamentally because if you have that $A^h$ is a symmetric matrix, you want that $A^{2h}=P^TA^hP$ is also a symmetric matrix. You want this because you want to again use the same kind of ...
- 54.1k
4
votes
Accepted
Implementing matrix term version of Gauss-seidel
The $L$ and $U$ of Gauss-Seidel are different from the $L$ and $U$ that come from the LU factorization. For Gauss-Seidel, $L$ and $U$ are what you get if you zero out the upper or lower part, ...
- 750
3
votes
How "sparse" should a sparse matrix be to see benefits?
This really comes down to what methods you are intending to use. If you store the matrix dense then you will use dense factorization routines, the cost of which will scale cubically with the matrix ...
- 3,263
3
votes
Accepted
Is there any other sparse matrix data in matlab built-in file?
There are many sparse matrices in Matrix Market
A visual repository of test data for use in comparative studies of
algorithms for numerical linear algebra, featuring nearly 500 sparse
matrices ...
- 2,192
Only top scored, non community-wiki answers of a minimum length are eligible