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.

1
vote
1answer
37 views

Optimality of block-Jacobi preconditioner

For a dense $N \times N$ matrix $A$, is the block-Jacobi preconditioner comprising the inverse of the diagonal blocks of $A$ the optimal block-diagonal preconditioner? Could there exist another matrix ...
1
vote
0answers
25 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 ...
0
votes
0answers
17 views

A preconditioner for self-consistent iteration

I tried to derive a preconditioner for self-consistent iteration similar to section IX in arXiv:0804.2583. For simplicity, consider here only one orbital (one or two electrons) systems. Suppose that ...
2
votes
1answer
96 views

In iterative methods, are matrix decompositions considered useful for implementation?

When we study an iterative method from textbooks, for example, see the Gauss-Seidel Method, the given matrix is decomposed with suitable splittings. In the example, $A = L+U$. So we can proceed with ...
2
votes
1answer
44 views

Blowup of error in Conjugate Gradient method with periodic Dirichlet Poisson matrix

My problem is that the L2-Norm of the residual for the periodic Poisson matrix $P$ is initially decreasing but starts to blow up after a certain number of iterations. The blowup happens earlier the ...
2
votes
1answer
62 views

Re-using LU factorization within iterative (?) setup for a sum of two matrices

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...
0
votes
0answers
52 views

Solving a non-convex optimization problem using fmincon

I am trying to solve a non-convex optimization problem using fmincon(). At each iteration, I am iteratively looking for the optimum value and when the termination ...
0
votes
1answer
27 views

PCJACOBI works but the default PCBJACOBI failed in PETSc

I am using PETSc and libmesh to solve a simple linear elastic problem with quite complicated geometry, using linear tetrahedral elements. I am always using the KSP CG as the solver. I noticed that ...
0
votes
2answers
86 views

Overrelaxation with w < 0

Are there any circumstances under which using a value $w < 0$ would help us find a solution in over-relaxation faster than we can with the ordinary relaxation method? Over Relaxation Method: $$x'=...
2
votes
0answers
60 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:...
0
votes
0answers
27 views

Boundary Conditions involving exponential functions of nodal unknowns

I am fairly new to Computational Engineering and I have mainly been exposed to using the Finite Difference Method to produce Linear Systems and solve them using Iterative Methods. I am trying to ...
1
vote
1answer
81 views

Conjugate gradient - ill-conditioning and numerical tolerance

I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method. Is ...
1
vote
1answer
41 views

Wrong results for $2$ stage multistep method $y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$

I need to fix a code to utilise the $2$ stage multistep method : $$y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$$ Since this is an implicit method, I used a Newton-Raphson ...
3
votes
0answers
78 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 ...
1
vote
1answer
121 views

Operation count for GMRES

One can use GMRES as it is, but there is also a version of GMRES called k-step restarted GMRES, which is used for large matrices, where $k$ is some fixed number of steps after which we take a new $x_0$...
4
votes
0answers
66 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 ...
8
votes
2answers
264 views

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

I'm a noob into eigenvalues algorithms, but something call my attention. QR algorithm works with real/complex matrices producing real/complex eigenvalues. However, it can not produce complex ...
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 ...
4
votes
0answers
163 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
141 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
67 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
102 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 ...
4
votes
1answer
118 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
58 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 ...
3
votes
0answers
65 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-...
1
vote
0answers
55 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
121 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 ...
0
votes
1answer
44 views

Time iteration no longer smooth after using scaled units

I have a time iteration function looked on a 2D surface like this. Since the numbers wee very small i.e. hbar=6.6260700404e-34./(2*pi), my professor told me to use our own "scaled unites" during the ...
1
vote
0answers
54 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
110 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
131 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 ...
1
vote
1answer
51 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} \...
2
votes
1answer
117 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)...
-1
votes
1answer
217 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 ...
2
votes
1answer
175 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
55 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
184 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 ...
1
vote
2answers
500 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
55 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
228 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 ...
0
votes
1answer
456 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
476 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
197 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\...
0
votes
1answer
241 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 ...
5
votes
1answer
807 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<...
3
votes
0answers
169 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
343 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|<...
4
votes
0answers
313 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
324 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
145 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 ...