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
1
vote
1answer
73 views

Iterative solution of ill-conditioned matrix systems

I want to solve a matrix system of the form $Ax=b$ where $A$ is ill-conditioned. The matrix system comes from a structural simulation problem which was discretized using finite elements. I do not have ...
0
votes
1answer
63 views

How to set an initial guess for the iterative solver in Comsol?

How to set the initial guess for the iterative solver GMRES or FGMRES for linear problems (Helmholtz equation of RF module) in Comsol?
4
votes
0answers
64 views

Complex differentiation of linear solvers

I have a linear system $$Ax=b$$ which I'm solving approximately, and I need to take the frechet derivative of x with respect to z. Were I solving the problem exactly (either analytically or to machine ...
2
votes
1answer
125 views

Why my parallel code using MPI is much slower than the serial one?

I know that is not the first time someone asks this question but I'm really confused.I'm new to MPI, and I tried to implement the Jacobi solver for a linear system $Ax=b$. I want to compare the time ...
3
votes
1answer
83 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
46 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
26 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
139 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
46 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
66 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
61 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
32 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
67 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
29 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
83 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
83 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
126 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
67 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
3answers
338 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
180 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
144 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
105 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
121 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
66 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
56 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
122 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
57 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
133 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
52 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
218 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
177 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
188 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
517 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
56 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
233 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
477 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
497 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
202 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
244 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
853 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
176 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 ...