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.
249
questions
3
votes
0answers
85 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-...
5
votes
0answers
436 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 ...
3
votes
1answer
172 views
Efficient implementation of preconditioners for iterative solvers
I am struggling a bit with the concept of preconditioners for iterative solvers and how to implement them efficiently. The literature mostly provides methods to create a preconditioner matrix $M$ (...
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 ...
3
votes
0answers
189 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 ...
0
votes
1answer
2k views
MATLAB: code for restarted gmres
I have a question about Matlab and restarted gmres. I would like to use gmres.m provided here. This code seems to be popular for the scientific computation newcomer....
4
votes
1answer
185 views
Convergence rate Jacobi/Gauss-Seidel with mesh resolution
In the book
A Multigrid Tutorial - Briggs, Henson. McCormick
in the beginning of Chapter 3, it is mentioned that
...because the convergence factor behaves as 1-$O(h^{2})$, the coarse grid ...
3
votes
1answer
59 views
why am I not getting a staircase for the rotation number?
I'm trying to understand the staircase map. Look at this map from the circle to itself:
$$ x \stackrel{F}{\mapsto} \big[\omega + x + \tfrac{\epsilon}{2\pi} \sin (2\pi x) \big] \pmod 1 $$
Such a map ...
7
votes
2answers
226 views
Lanczos algorithms for Hermitian system with Toeplitz kernel
Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector ...
6
votes
2answers
287 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 ...
1
vote
0answers
60 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 ...
2
votes
1answer
474 views
Finite Elements: using preconditioned conjugate gradients with incomplete cholesky decomposition
I have to write a little finite elements code in C.
I was asked to implement the conjugate gradients method, which I have done. Now, I am looking to improve further the efficiency of my program by ...
-1
votes
1answer
278 views
Gauss-Seidel method convergence
I am currently programming a code to find the equilibrium function that satisfies the poisson equation in 2D. In order to do this I use finite difference methods and the discrete equation I want to ...
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
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
1answer
120 views
Questions about iterative projection methods in Saad book
I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results.
In the statements of the propositions, what does it mean ...
4
votes
2answers
143 views
Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights
In the problem I am dealing with, I require to repeatedly solve $Ax=b$ where $A$ is a weighted Laplacian matrix of a sparse graph. The right-hand side remains constant. However each time I solve the ...
5
votes
1answer
242 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 ...
1
vote
1answer
56 views
Optimal algorithm choice for mixed diagonal/dense problem
$$
\text{Let}\\
A, B \in \mathbb{C}^{n \times n} \text{ and } \hat{\alpha}, \hat{\beta} \in \mathbb{C}^{n}, \hat{f} \in \mathbb{C}^{2n}
\\
\text{Find }\\
\underline{\mathbf{x}} \in \mathbb{C}^{2n} \...
13
votes
1answer
310 views
Non-monotonic convergence in fixed-point problem
Background
I am solving a variant of the Ornstein-Zernike equation from liquid theory. Abstractly, the problem can be represented as solving the fixed point problem $A c(r)=c(r)$, where $A$ is an ...
2
votes
1answer
172 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)...
3
votes
1answer
361 views
How to show that Gauss-Seidel iterative method is equivalent to successively setting each component of residual vector to zero?
As stated in the title, it's said in the book that Gauss-Seidel iterative method is equivalent to successively setting each component of residual vector to zero. After rearranging G-S scheme, I got ...
2
votes
1answer
67 views
Implicit solution to Sylvester equation
Suppose a matrix $M\in\mathbb{R}^{n\times n}$ is defined as the solution to a Sylvester equation $$AM+MB=C,$$ for some fixed (known) matrices $A,B,C$. In the regime where $n$ is large, we may with ...
1
vote
0answers
269 views
Why does PETSc take unexpectedly long to set up its KSP solver with a custom preconditioner? [closed]
I am attempting to solve a large system, $\bf{Ax} = \bf{b}$ with the help of PETSc. Due to the size of the problem, I'm using a matrix-free approach, where $\bf{A}$ is just a shell. I'm also providing ...
9
votes
4answers
1k views
What is a robust, iterative solver for large 3-d linear-elastic problems?
I'm diving into the fascinating world of finite element analysis and would like to solve a large thermo-mechanical problem (only thermal $\rightarrow$ mechanical, no feedback).
For the mechanical ...
5
votes
1answer
1k views
Newton's method with box-constraints
I have to use an iterative method (Newton-Raphson, modified Newton and Broyden) to solve a system of nonlinear equations $f(x)=0$. Every unknown $x_i$ is bounded between $l_i$ and $u_i$, i.e., $l_i<...
9
votes
1answer
3k 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 ...
1
vote
2answers
768 views
Linear solvers: How to deal with a singular system? (Poisson equation with Neumann boundary conditions)
The question is in the context of iterative numerical solution of large PDE systems with Finite Differences or Finite Elements:
Stating the Poisson equation with Neumann boundary conditions will lead ...
2
votes
0answers
68 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 ...
3
votes
3answers
295 views
For which problems Krylov subspace methods are preferred over multigrid methods?
As multigrid methods are known to have grid independent convergence rates with $O(N)$ computational cost, then why would one be interested in using Krylov subspace methods at all, for which ...
2
votes
1answer
935 views
Set of linear ordinary differential equations with a mass matrix
What methods are known for efficiently solving a large set of linear homogeneous ordinary differential equations of the following form?
\begin{equation}
\mathbf{B} \frac{d\mathbf{y}}{dt} = \mathbf{A} \...
1
vote
2answers
833 views
Is it necessary to invert precondition matrix for iterative solver?
I was reading these slides about preconditioners. I believe I grasp the idea of how they work but there is something that is still not making sense.
If we have the system $Ax=b$ and use a ...
4
votes
2answers
241 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
1answer
320 views
A question about GMRES
We know that if the matrix $A$ is symmetric positive definite, the FOM (full orthogonalization method) and the GMRES are theoretically equivalent to the CG (conjugate gradient) and the CR (conjugate ...
2
votes
1answer
626 views
Stopping criteria in iterative methods for solving nonlinear equations
Is it a good criterion to stop iterative methods for solving non-linear equations, such as Newton-Raphson and good Broyden's methods, when $|x_k-x_{k-1}|<|x_k|\,reltol + abstol$ OR when $|f_k|<...
0
votes
1answer
345 views
Example Problem to Demonstrate BiCGStab
So our team has been able to code up a BiCGStab implementation for a class project, and we'd like a potential example problem to try it out on.
So far, we've talked about a 1D Laplacian with Neumann ...
3
votes
0answers
254 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 ...
4
votes
0answers
489 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 :
$$ ...
2
votes
1answer
429 views
Fastest way to solve a sparse unsymmetric system many times
I have to solve a system $Ax^{(n)} = b^{(n)}$ many times, $A$ being a sparse (pentadiagonal in most part of its structure), unsymmetric, constant matrix.
Currently, I am performing the LU ...
0
votes
1answer
340 views
Obtaining extra output argument(s) from the objective function used by fsolve in MATLAB
I have a MATLAB code (see below) that employs 'fsolve' from the optimization toolbox for a root finding problem.
The bottleneck is that, within the objective function calculation, there is a ...
3
votes
1answer
2k 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 ...
2
votes
2answers
540 views
PageRank using Inverse Iteration Method by Cleve Moler
I was trying to understand how to use the inverse interation method to compute the page rank as an exercise.
In this chapter (page 4) about page rank (by Cleve Moler), the author suggests to use the ...
0
votes
1answer
192 views
Iterative methods to solve linear system in 3D FEM
I implemented a FEM solver in MATLAB for Poisson's equation in 3D, using hexahedron and sparse matrix for the Laplacian. I was using the backslash but now I have to use a few iterative methods (GMRES ...
5
votes
1answer
281 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
0answers
179 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 ...
1
vote
1answer
660 views
Jacobi iteration for finite difference: when to stop?
I implemented a finite difference scheme to solve Poisson's equation in a 2D grid in C. I solve the system by using Jacobi iteration. Everything works fine until I use a while loop to check whether it ...
2
votes
1answer
138 views
Regarding impractical usage of direct solvers of linear systems [closed]
Since the computational complexity of direct elimilation methods for solving linear systems is $O(n^3)$, it's not practical when the number of dofs is large. But how large would you call it a large ...
2
votes
0answers
152 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 ...
1
vote
1answer
7k views
Implementation of the Jacobi iteration to find the solution to $Ax = b$
I implemented the Jacobi iteration using Matlab based on this paper, and the code is as follows:
...
1
vote
1answer
161 views
Difference between explicit and implicit preconditioning
What is the difference between an explicit and implicit preconditioner?
