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.
54
questions with no upvoted or accepted answers
7
votes
0answers
494 views
DIIS method to accelerate SCF convergence for stretched geometries
I am implementing from scratch an Hartree-Fock calculation in the STO-3G basis set to perform Born-Oppenheimer molecular dynamics. I have a Restricted Hartree-Fock procedure that can reproduce very ...
6
votes
0answers
65 views
Implementation of Lanczos method that returns tridiagonal matrix
The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
5
votes
0answers
735 views
Can Gauss-Seidel/SOR (preconditioned?) be applied to a non-diagonally dominant matrix?
After applying finite difference method to a Laplace/Poisson problem always arises a diagonal dominant system of equations that can be solved with Gauss-Seidel or SOR methods. If the original PDE does ...
5
votes
0answers
190 views
Conjugate residual/gradient convergence checking in practice
Let's say we want to solve $Ax=b$ ($A$ symmetric positive /semi/definite) with the conjugate residual/gradient method. $A$ comes from FEM where the mesh is being refined. The exact solution is $x_*$ ...
5
votes
1answer
237 views
Robust smoothers for geometric multigrid
I'm searching for robust smoothers for geometric multigrids.
By robust I mean:
Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin),
Parallel (suitable for ...
4
votes
0answers
89 views
Trying to understand splitting-based iterative method for 2D Laplace problem
I am trying to understand the theory behind a splitting based iterative method which uses the incomplete Cholesky factorization. Before giving the specific details, let me first give the problem ...
4
votes
0answers
75 views
Improving convergence of Jacobi iteration to Schur form
I'm using SIMD processor arrays to compute the eigen-decomposition for large numbers of small (up to $32\times 32$) matrices. For assorted technical reasons, Jacobi iteration maps well to the SIMD ...
4
votes
0answers
342 views
Solving a PDE implicitly by iteration in python
Connected to this question here on Computational Science, I've posted a follow-up question on how to solve a PDE using an implicit scheme like Crank-Nicholson in general in this question on SO.
But I ...
4
votes
0answers
437 views
Convergence rate of Picard iterations
Given a first order ODE $y'(x)=f(x,y)$ with the initial condition $y(x_0)=x_0$ such that it satisfies Picard thoerem of existence and uniquness, one can compute the solution by Picard iterations :
$$ ...
4
votes
0answers
160 views
Preconditioning technique for large sparse non-hermitian matrix
I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
4
votes
0answers
147 views
What causes periodic humps in residual plots?
When using many iterative methods, whether for solving linear systems, looking for steady-state convergence in CFD, etc., the semilog plot of the residual often shows "humps" as the residual decays. ...
4
votes
0answers
478 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, ...
4
votes
0answers
332 views
Understanding the meaning of Computational Order of Convergence
I am a postgraduate student with interest in numerical methods for solving nonlinear systems of equations. I have read some papers that discussed about 'computational order of convergence' for some ...
3
votes
0answers
44 views
Subspaces for Iterative methods
In the original paper of Conjugate Gradients, the authors mention that if we pick the canonical basis $\{e_1,e_2,\ldots,e_n\}$, to obtain A-orthonormal vectors, we end up with the Gaussian elimination ...
3
votes
0answers
185 views
Nonlinear least squares and regularization
Consider the nonlinear least-squares minimization of a vector of $n$ residuals $\mathbf{f}$ in $p$ parameters $\mathbf{x}$:
$$
\min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2
$$
This can be done with ...
3
votes
0answers
156 views
Unstable convergence of a Poisson equation
What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
3
votes
0answers
80 views
PETSc SNES for user defined state
How to use PETSc SNES (scalable nonlinear equation solver), when the solution is not a vector but a user defined state?
I am implementing a non-linear mechanics problem (geometrically exact shell 5-...
3
votes
0answers
230 views
How to avoid the Broyden's jacobian approximation becoming poorer with the number of iterations?
I have to solve many times a nonlinear system of the form
$$f(x) = b^{(n)}$$
inside a loop.
The function $f$ is expensive to compute and I do not have its jacobian, so I have tried the good Broyden's ...
2
votes
1answer
44 views
Project to nearest point on convex polyhedron
I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces:
$$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
2
votes
0answers
64 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
0answers
68 views
How to reproduce the numerical examples in Prof. Saad's Book about Krylov subspace methods?
After reading Prof. Saad' Book, "Iterative methods for Sparse Linear Systems, 2nd version", I want to do the numerical examples about the Krylov subspace methods not only to reproduce the results in ...
2
votes
0answers
87 views
Small residual but wrong results
When I use BiCGStab to solve a linear matrix system, I use the relative residual to exit the iteration and output the results. For calculating the relative residual I divide the norm of vector $r$ ...
2
votes
0answers
104 views
Understanding MP-PIC implementation in OpenFOAM
The multiphase particle-in-cell (MP-PIC) method is characterized by mapping particle properties from the Lagrangian coordinates to the Eulerian grid. However, the implementation of this method in ...
2
votes
0answers
117 views
Richardson's Iteration, Gradient Method and Spectral Radius
Richardson's iteration introduce a scalar $\alpha$ to the update formula:
$$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)} $$
And compute $\alpha$ by minimizing the spectral radius:...
2
votes
0answers
69 views
Simultaneous update to barycenters
Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.
Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
2
votes
0answers
61 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 ...
2
votes
0answers
143 views
Generalized eigenvalue with null space
Define $S\in\mathbb{R}^{n\times n}$ as
$$S:=H+Q^\top V^{-1} Q.$$
$H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for ...
2
votes
0answers
77 views
Numerical error in implementation of iterative algorithm
I am trying to implement (in Python for now) low thrust orbit propagation for spacecraft using universal variables. For a given central body with the gravitational parameter $\mu$ and an orbit with ...
2
votes
0answers
65 views
Dynamic Successive Over/under Relaxation (SOR) with several variables
I am solving a partial differential algebraic equation (PDAE) system which has the following dependent variables:
$f=f(X,T)$ and $g=g(T)$, along with a few others
My current method for coupling is ...
2
votes
0answers
52 views
SPECT reconstrction using MLEM
In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
2
votes
0answers
218 views
Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?
I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
2
votes
0answers
106 views
Modal analysis of structure with aerodynamic damping
I'm using modal decomposition to predict the steady state response of a beam structure to harmonic loading. The structure itself is very lightly damped, but we know from experiments that the ...
2
votes
0answers
71 views
What are Implications of Commutative Diagrams?
This question may be too broad. But I really want to know some concrete explanations. I often find various commutations appear here and there, which concerns the application order of two operators. ...
1
vote
0answers
59 views
Bifurcation points on homotopy path by numerical continuation?
I am trying to implement an algorithm that finds (possibly) all solutions of a system of nonlinear polynomial equations $$F(X) = 0$$ I thought about using the (convex) homotopy $$H(X,T) = TF(X) + (1-T)...
1
vote
0answers
59 views
Can the standard multigrid performance be used for time-dependent PDEs?
Consider a time dependent pde(i.e u(x,t)).I know when only space-coarsening is used the standard multigrid performance can be applied but what if instead we use only time-coarsening?Can we apply the ...
1
vote
0answers
37 views
BicgStab is not able to solve while Jacobi or GaussSeidel Methods can
I am trying to solve the 2D laplace equation,
$\frac{\partial^2 T}{\partial x^2} + \frac{\partial^2 T}{\partial y^2} = 0; \qquad 0 \lt x \lt 1, \quad0 \lt y \lt 1$
Subjected to the boundary ...
1
vote
0answers
54 views
Kinetic preconditioning
Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step.
IX. PRECONDITIONING
As already mentioned, ...
1
vote
0answers
34 views
Logging vs outputs in iterative optimisation
I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
1
vote
0answers
59 views
Fixed point iteration reduction factor
In a book for solving a nonlinear differential equation with $N+1$ points, $u_{xx} = e^{u}, u(-1)=u(1) = 0$, in $[-1,1]$ with homogeneous Dirichlet boundary conditions, the fixed point iteration is ...
1
vote
0answers
64 views
fourth order Poisson iterative solver --in Matlab
I want to calculate the stream function $\psi$ starting from a velocity field $(u,v)$ (such that $u=-\frac{\partial\psi}{\partial y}$ and $v=\frac{\partial\psi}{\partial x}$). I thus calculate the ...
1
vote
0answers
56 views
bound error for iterative method for solving linear system
$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that
$$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
1
vote
0answers
32 views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
1
vote
0answers
153 views
Search Direction in Conjugate Gradient
Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
1
vote
0answers
86 views
Increase convergence of non-linear equations resulting from ODEs
I am trying to solve a set of couple ODEs:
$V_l(r) - r W_l(r) - f1(r) W_l' = 0\tag 1$
$r^2 h''_l(r) + f2 r h_l'(r) + f3 h_l(r) - f4 U_l(r) = 0 \tag 2$
$\kappa (U_l + h_l) + V_{l+1} + W_{l+1} = 0\...
0
votes
0answers
29 views
The error in SOR algorithm suddenly falls to zero when it reaches 1e-7 range
I am solving the Poisson equation for heterojunction using Fortran90. I use the SOR algorithm to arrive at the potential profile.
I see the weird behavior where the error (the difference between the $...
0
votes
0answers
53 views
Preconditioning the $[1 \quad-2 \quad 1]$ Finite Difference matrix
Let $A$ be the well known tridiagonal matrix coming from the 1D Finite difference discretization of the Laplacian, with stencil $\frac{[1 \quad-2 \quad 1]}{h^2}$.
The system $Ax = b$ is very large, so ...
0
votes
0answers
58 views
fixed point iteration on DD method
I have to solve the the problem $u_t+\Delta^2u=f(u)$, where $f(u)$ is non-linear, using domain-decomposition method.
My approach is first using fixed point iteration on mixed form i.e to say $u^{k+1}...
0
votes
0answers
73 views
Solving a nonlinear problem with a very small components with finite element method
In solving nonlinear hyperelastic solid mechanics problems, to converge to the correct solution we need to do step-by-step loading which makes the deformation at each step very small (for my ...
0
votes
0answers
63 views
A name for a numerical phenomena when using numerical methods
I have a nonlinear solver for equation $g= c_1f(x_1,y_1)+c_2f(x_2,y_2)$. Note that $c_1$ is much bigger than $c_2$. So after using Levenberg–Marquardt algorithm, I could only get $x_1$, $y_1$ and $...
0
votes
0answers
42 views
Why does the initial guess for linear system usually choose by zero vector?
For solving linear system
$$
Ax=b,
$$
using iterative mehods, we often use the terminate criterion as follows:
$$
\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps.
$$where $x_0$ is the ...
