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.

Filter by
Sorted by
Tagged with
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?