Questions tagged [iterative-method]
A method which produces a sequence of numerical approximations which converges (provided technical conditions are satisfied) to the solution of a problem, generally through repeated applications of some procedure. Examples include Newton's method for root finding, and Jacobi iteration for matrix-vector solves.
29
questions
30
votes
2
answers
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 ...
10
votes
1
answer
4k
views
full rank update to cholesky decomposition
Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate
$det(A)$
$A^{-1}X$ for some ...
40
votes
3
answers
18k
views
How to choose a method for solving linear equations
To my knowledge, there are 4 ways to solving a system of linear equations (correct me if there are more):
If the system matrix is a full-rank square matrix, you can use Cramer’s Rule;
Compute the ...
11
votes
1
answer
8k
views
Are there any heuristics for optimizing the successive over-relaxation (SOR) method?
As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
12
votes
1
answer
1k
views
Smallest eigenvalue without inverse
Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly.
Is there an iterative algorithm for finding the ...
9
votes
3
answers
1k
views
Iterative methods for indefinite systems without block structure
Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form
$$\begin{pmatrix} A & B^t \...
4
votes
1
answer
109
views
Stochastic cellular automata - algorithm limited by 1 cell per timestep
Context
Let's say I am trying to model the spread of mold in a petri dish, using a stochastic cellular automata approach. The petri dish can be thought of as a grid of 1mm x 1mm squares, each called ...
18
votes
1
answer
2k
views
Intuitive motivation for BFGS update
I am teaching a numerical analysis survey class and am seeking motivation for the BFGS method for students with limited background/intuition in optimization!
While I don't have time to prove ...
17
votes
1
answer
3k
views
Can a Krylov subspace method be used as a smoother for multigrid?
As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
11
votes
2
answers
1k
views
Which iterative linear solvers converge for positive semidefinite matrices?
I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$
(...
11
votes
2
answers
365
views
What is the underlying structure of scientific code performance?
Consider two computers with different hardware and software configurations. When running the exact same serial Navier-Stokes code on each platform it takes x and y time to execute one iteration for ...
10
votes
1
answer
513
views
Solving a system with a small rank diagonal update
Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
10
votes
2
answers
2k
views
Safe application of iterative methods on diagonally dominant matrices
Suppose the following linear system is given
$$Lx=c,\tag1$$
where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
7
votes
1
answer
974
views
full rank update to cholesky decomposition for multivariate normal distribution
This question is a specialization of full rank update to cholesky decomposition, to which I hope to get a more positive answer.
When calculating the minus log of the multivariate normal distribution, ...
6
votes
1
answer
965
views
Inverse iteration to find the null singular vector of a rank-deficient matrix
I have an $n \times n$ unsymmetric matrix $A$ that results from the discretization of an ill-posed Poisson problem, and thus is rank-deficient with null space of dimension one. I want to compute just ...
6
votes
2
answers
325
views
Krylov subspace iterative methods in floating point arithmetic
Is there any work that considers Krylov subspace iterative methods in floating point arithmetic? I'm especially interested in how rounding errors influence the convergence and the accuracy of the ...
5
votes
1
answer
350
views
Convergence of Jacobi's method for a semilinear elliptic PDE
I have an iterative finite difference scheme for the Poisson equation
$$
\nabla^2 u=-\rho
$$
It's the Jacobi method, which has the form (for 1D systems)
$$
u^{n+1}_{i} = \frac{1}{2}(u^n_{i+1} + u^n_{...
5
votes
2
answers
331
views
Preconditioner for the GMRES method in the Uzawa algorithm
I'm trying to solve
\begin{equation}\left\{
\begin{split}
\frac{\partial u}{\partial t}+(u\cdot\nabla)u-\nu\Delta u+\frac1\rho\nabla p&=f\;\;\;\text{in }\Lambda\\
u&=0\;\;\;\text{on }\partial\...
5
votes
2
answers
412
views
Recurrence relation for matrices
I have matrices ($S_0$ thought $S_N$) and I have a recurrence relation that link successive matrices together.
$$S_i + S_i(aS_{i-1}^{-1})S_i=C_i+aS_{i+1}$$
We can assume for this problem that $S_0=S_N=...
4
votes
1
answer
4k
views
Iteratively solving 3D Poisson equation in MATLAB
I have written a function that sets up a sparse matrix A and RHS b for the 3D Poisson equation in a relatively efficient way. The set-up is nothing fancy: I have extended the 2D 5-point stencil to an ...
4
votes
2
answers
2k
views
What is the difference between "Newton-type" and "Newton-like" iteration?
Is there any clear classification between different iterative methods?
What is the difference between Newton-type and ...
4
votes
1
answer
177
views
Factorization for reweighted least squares
I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares
Essentially this requires solving a number of least-...
3
votes
2
answers
699
views
Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?
Recently, I have met a question that
a saying goes that for large linear system: iterative methods are required because of memory problem of direct methods.
But when I implement some experiments ...
3
votes
1
answer
518
views
Designing a preconditioner for a very Ill-conditionned matrix
I am a physicist with limited numerical methods knowledge and I am trying to speed up the inversion of a very ill-conditioned problem ($rcond>10^{30}$). The same sparse square matrix is used ...
2
votes
0
answers
400
views
Residual of Poisson equation with periodic boundaries
I am trying to write a multigrid solver for Poisson's equation, $-\Delta u=f$, on the unit square, $\Omega=(0,1)^2$ with periodic boundaries. My primary source has been Multigrid by Trottenberg, ...
2
votes
1
answer
111
views
Iterative solution for a minimization problem involving matrix equations
I have a real valued function $F$ for which I am looking to find its global minimum. The function is well behaved and I can obtain its Jacobian. I could also compute the Hessian but the function ...
2
votes
1
answer
272
views
Solving sparse least squares system with limited memory
This was a question on a past final that we can't figure out. Take the least squares system
$$\min_x ||Ax-b||_2\, ,$$
where $A\in\mathbb{R}^{mxn}$, $m<n$, and A is full rank. A has $\mathcal{O}(n)...
2
votes
0
answers
85
views
How can I numerically solve a saddle point problem with repeated constraints?
I am interested in numerically solving the following constrained minimization problem; Find the value of $x\in \mathbb{R}^n$ that minimizes $f$ where
$f\colon \mathbb{R}^n\to \mathbb{R}$ is defined ...
0
votes
1
answer
194
views
Can successive over-relaxation (SOR) method deal with ill-posed PDE BVP?
Recently, I've been struggling to understand the limitations and capabilities of the successive over-relaxation (SOR) method for boundary value problems which are ill-posed, such as, for instance, ...