14 votes
Accepted

Smallest eigenvalue without inverse

Compute the largest-magnitude eigenvalue $\lambda_{max}$ of $A$ (with, say, eigs('lm')). Then compute the largest magnitude (negative) eigenvalue $\hat{\lambda}_{...
user avatar
  • 2,096
14 votes
Accepted

Quality of eigenvalue approximation in Lanczos method

The convergence behavior you are seeing is actually expected. One of things that makes the Lanczos method so interesting is that it does a good job of simultaneously converging eigenvalues at both ...
user avatar
  • 5,734
13 votes
Accepted

How does the QR algorithm applied to a real matrix returns complex eigenvalues?

In a nutshell, the QR algorithm applied to a matrix $A$ is an iterative procedure that converges to the real Schur decomposition: a unitary matrix $Q$ and a matrix $R$ in block upper triangular form (...
user avatar
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,287
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
11 votes
Accepted

Markov (Chain) image generators?

I've implemented this recently, basically it counts how many times each specific colour borders another colour to make up a frequency table. To generate an image, a random colour and position are ...
user avatar
  • 226
10 votes
Accepted

How can a CG solver solve a non positive definite sparse matrix

I highly recommend the following read: J.R. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain" In short, if the matrix is non-positive definite, there is no ...
user avatar
  • 8,287
10 votes
Accepted

Is there an iterative solver for dense matrices with possible zero diagonal entries?

Iterative Krylov-subspace solvers generally only require matrix-vector products and don't care whether or where there are zeros in the matrix. In your case, unless you have other information about the ...
user avatar
9 votes
Accepted

Solve linear system with Newton-Raphson method

Yes you can do this, and it will converge in one iteration regardless of the starting value. This is because each step of Newton's method involves solving a linear system with the Jacobian of the ...
user avatar
9 votes
Accepted

Why MATLAB chooses the Householder in its built-in function gmres.m?

If you're using GMRES, typically you have a large stiff system. The extra work done for the householder algorithm is negligible compared to the expense of GMRES and the preconditionder. As such, we ...
user avatar
  • 1,862
8 votes
Accepted

Eigenvalues of a sparse banded nonsymmetric matrix from an elliptic operator

The simple answer is that you would use inverse iteration (subspace or with deflation). This is basically the power method (repeatedly multiplying the matrix by a vector and normalizing, singling out ...
user avatar
  • 4,400
8 votes

Direct or iterative solver for ill-conditioned problems

Your question really doesn't admit a simple answer—we need to know more specifics about your problem to provide a useful answer. In general, iterative methods can be faster than direct factorization ...
user avatar
8 votes
Accepted

How to solve the problem without using symbolic computation

You can solve this numerically in Python without symbolic computation. from __future__ import print_function, division import numpy as np from numpy import exp from scipy.integrate import quad from ...
user avatar
8 votes
Accepted

Efficient implementation of preconditioners for iterative solvers

I don't particularly care for the notation $M^{-1}$ precisely because of the confusion you find yourself in. I (and others) simply call the preconditioner $P$. The point, however, is that for ...
user avatar
7 votes
Accepted

How to evaluate a series of derivatives?

You can convert $\mathbf{b}-\mathbf{x}$ into polar coordinates, and do the dot product in this system. This changes $((\mathbf{b}-\mathbf{x})\cdot\nabla)^n\frac{1}{r}$ to $$\left((\mathbf{b}-\mathbf{...
user avatar
7 votes

What are some reasons that Conjugate Gradient iteration does not converge?

If your matrix is symmetric, positive definite, the CG method may converge slowly, but it converges for $n\to\infty$. The only reason it does not converge on a computer are round-off errors, in ...
user avatar
7 votes

Operation count for GMRES

Performing $k$ steps of GMRES uses $O(n k^2)$ time and $O(n k)$ memory. In other words, the algorithm gets more and more expensive with each additional iteration. In theory, the algorithm terminates ...
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
6 votes

How many generations does it typically take for a differential evolution method to reach a global optimum?

I don't think there's enough information to give a heuristic like, "in general, it takes $k$ iterations for differential evolution to reach a global optimum". First, we don't know how many iterations ...
user avatar
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,287
6 votes

For which problems Krylov subspace methods are preferred over multigrid methods?

The answer depends somewhat on the discretization; for example, some boundary integral discretizations result in very well-conditioned matrices, for which a Krylov solver works just fine without ...
user avatar
  • 2,961
6 votes
Accepted

Finite Elements: using preconditioned conjugate gradients with incomplete cholesky decomposition

While preconditioned CG with incomplete Cholesky (ICC) is reasonably straightforward to formulate mathematically, writing an efficient implementation is a non-trivial matter. Here's some of the ...
user avatar
  • 2,096
6 votes

Why my parallel code using MPI is much slower than the serial one?

The first thing you need to ask yourself: is your problem big enough that the overhead of MPI messaging is less than the work that you save. Your problem size is 10k which is small, but on the other ...
user avatar
6 votes
Accepted

Iterative linear solver for "ugly" saddle point system

You should stick with GMRES, it is the only method that is essentially guaranteed to get a solution here. The real problem appears to be you need a better preconditioner. You could try sticking with ...
user avatar
  • 1,862
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
6 votes

Why minimizing with respect to A-norm?

Wolfgang Bangerth's answer already says almost everything, but another subtle detail is that GMRES/MINRES minimize the norm of the residual, i.e., $\|Ax_k-b\|$, while CG minimizes the (A-)norm of the ...
user avatar
5 votes

How to choose a method for solving linear equations

The Eigen Library Documentation also has a nice overview page with a lot of information about different matrix decompositions: http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions....
user avatar
  • 435
5 votes
Accepted

Sort of problems where SOR is faster than Gauss-Seidel?

The convergence of classical iterative solvers for linear systems is determined by the spectral radius of the iteration matrix, $\rho(\mathbf{G})$. For a general linear system, it is difficult to ...
user avatar
5 votes
Accepted

Solving sparse linear equations with an iterative, out-of-core algorithm

For a sparse parallel solver, it's your own responsibility to provide a matrix vector product and a suitable preconditioner. The data for the vector itself should fit into main memory in any case. If ...
user avatar

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