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
7
votes
2answers
242 views

Is there an iterative solver for dense matrices with possible zero diagonal entries?

Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
1
vote
1answer
44 views

2D heat equation in both steady state and Transient state using iterative solvers

While solving a 2D heat equation in both steady-state and Transient state using iterative solvers like Jacobi, Gauss seidel, SOR. Should the answers, I mean the converged results of Temperature ...
4
votes
1answer
135 views

Without positive definiteness, does an iterative solver work?

Question Does lacking positive definiteness of the matrix of coefficients in a system of equations, make using iterative solvers impractical? Description Using the finite volume method, I have ...
0
votes
0answers
57 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}...
3
votes
1answer
65 views

Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?

I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ...
1
vote
2answers
61 views

Solution of symmeric/non-symmetric linear system

I would like to understand what happens in the following: I have a really simple Poisson problem, in 1D, with $u_0 = u_N = 0$. I assembled the stiffness matrix and the right-hand side, and I applied ...
1
vote
0answers
57 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)...
2
votes
1answer
32 views

Calculating coarse grid matrix in geometric multigird

The coarse grid matrix is calculated via RAP where R,P are the restriction and interpolation matrix,respectively.By checking a typical MG algorithm I want to ask how to calculate efficiently coarse ...
0
votes
1answer
38 views

Fixed-point iteration when image and domain are not the same

I have a function $f(x)$ defined on a domain $D$, but such that the image $f(D)$ may contain extra regions not included in its domain. I am interested in solving the fixed-point equation $x=f(x)$. If ...
4
votes
2answers
65 views

MInimizing cost function using iterative search for a minimum method

I want to estimated the parameters $\ \hat{\theta} $ of a model using an iterative search for the minimum of a cost function. The cost function is defined as follows: $$ V_N(\hat{\theta}) = \frac{1}{...
-1
votes
1answer
97 views

How to implement the Hessenberg QR Algorithm?

For context, I'm creating a linear algebra library from scratch for learning purposes in C. Right now I'm working on calculating eigenvalues but my implementation of the QR Algorithm is diverging. ...
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 ...
2
votes
2answers
96 views

What online optimisation algorithm can be used for a noisy cost function?

I am trying to optimise a function, but the function can be noisy and give varying results for the same parameters. Furthermore, it needs to be online, as the data from each new iteration happens ...
2
votes
1answer
81 views

Best way to check if SOR solution has converged for 2d matrix

I have written a SOR algorithm to solve the Laplace equation on a 2d grid. The outside of the grid is fixed at 0 and the central square is fixed at 10. I can obtain the fully converged solution for ...
2
votes
1answer
116 views

How to solve for f(A)x=b without GMRES?

How to solve for $f(A)x=b$? For GMRES, an answer is given in this book chapter: http://link.springer.com/chapter/10.1007%2F978-3-642-58333-9_2. Ungated version: https://www.researchgate.net/profile/...
2
votes
0answers
61 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, ...
1
vote
1answer
64 views

How the number of pre-smoothing and post-smoothing steps affect the asymtotic convergence rate of geometrical Multigrid?

Does the convergence rate of multigrid depend on the total number of smoothing steps or on the number of pre and post smoothing steps seperately?
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 $...
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 ...
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 ...
5
votes
1answer
475 views

Why MATLAB chooses the Householder in its built-in function gmres.m?

Recently, I have studied how to construct an orthonormal basis for Krylov subspace to solve $Ax=b$, where $A\in \mathbb{R}^{n\times n}$ is nonsingular. As we know, there are usually 4 ways to ...
2
votes
2answers
75 views

How to understand the choice of Krylov subspace orthonormal basis?

This semester, I study the Krylov subspace iterative methods (about Ax=b) using the book H. A. Van der Vorst. Iterative Krylov Methods for Large Linear Systems, volume 13. Cambridge University Press, ...
2
votes
1answer
162 views

What's wrong with the **PCG and MINRES** in matlab?

Last week, I have learned the details of the robust iterative methods of PCG, MINRES, GMRES, which will converges to the exact solution $x^*$ of nonsingular system within $N$ steps for $A\in \mathbb{R}...
1
vote
2answers
96 views

When should I write a matrix-vector function to handle the sparse matrix vector multiplication?

This semster, I have been studying the iterative methods for large sparse matrix system. But I have some questions. For large sparse matrix, we must use an economic storage to store them. The most ...
3
votes
1answer
51 views

Does the k-th approximate solution of a stationary iteration belong to the k-th Krylov subspace?

For an stationary iteration method solving $Ax=b$ as follows: $$ Mx_k = Nx_{k-1}+b, $$ I have known that when $M = I$, i.e., the Richardson iteration, the k-th solution $x_k = x_{k-1}+r_{k-1}$ is in ...
2
votes
1answer
60 views

What is the standard, extrapolation, and modified version of Richardson iteration method?

I have been studying the iterative methods recently. For classical iterative methods solving $Ax=b$, I have seen that the most simplest iteration method is the so-called "Richardson iteration". But I ...
2
votes
1answer
124 views

Why Krylov subspace iterative methods are faster than classical iteration?

This semester, I have been studying the most popular iterative methods, i.e., Krylov subspace iteration methods. For a large sparse system linear $$ Ax=b, $$ where $A$ is nonsingular, I know that ...
1
vote
1answer
70 views

Why do not we choose the error solution norm as an iterative method's criterion?

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 ...
0
votes
0answers
37 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 ...
0
votes
1answer
61 views

How to implement Geometric Multigrid in non-rectangular grids?

It is quite easy to implement multigrid on a rectangular grid but what about an non-rectangular?How to coarse a non-rectangular grid and apply multigrid(assume an easy non-rectangular grid capital ...
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
1answer
60 views

Are there any other better methods than block diagnoal and block upper triangular precondtioner for saddle point problems?

For stokes problems, $$ -\Delta \vec{u} + \nabla p =\vec{f},\qquad \nabla . \vec{u} = 0; $$ with appropriate boundary conditions which guarantee there is a unique solution. Using FDM or FEM, ...
3
votes
1answer
80 views

What is the **contraction factor and convergence factor** of a iteration method?

For any iteration method from A=M-N, e.g., $$ Mx_{k+1}=Nx_{k}+b,\quad k=0,1,... $$ we know that it converges iff $\rho(M^{-1}N)<1$. And when it converges, there exists a concept called asymtotic ...
1
vote
1answer
167 views

How suitable is multigrid method for time-dependent PDEs?

For elliptic PDEs (Poisson-type), the multigrid method is very sufficient, but how about time-dependent problems (i.e parabolic or hyperbolic PDEs)? Is it efficient to solve such problems using a ...
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 ...
2
votes
2answers
75 views

Can a direct method like Thomas be used in a multigrid method as a smoother?

As far as I know, multigrid uses stationary iterative methods as smoothers (i.e GS), but can we use a direct method also? For example, in case we have a tridiagonal system (for example 1D heat ...
1
vote
1answer
99 views

Solve linear system with Newton-Raphson method

Is it possible to solve a linear matrix system $A x = b$ using the Newton-Raphson method? If yes, how can this be done? More special, how is the derivative build?
4
votes
1answer
75 views

Low rank update of QR of inverse

I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step: Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$ ...
2
votes
2answers
171 views

Does iterative method work for singular consistent linear system Ax=b?

Recently, I have been studied iterative methods for large sparse linear system Ax=b, where A is nonsingular, so there is a unique solution x. And the stopping criterion is usually chosen with norm(b-...
0
votes
0answers
38 views

Divergence issues when using intrinsic cohesive elements approach

When I model the strain localisation of a microscopic sample (or say RVE ) with cohesive elements approach, the convergence performance looks very terrible. I have to use extremely time increments (...
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
2answers
127 views

Evaluation of slope at iteration ith - Newton-Raphson method

I'd like to know how Ansys computes the slope (=stiffness matrix) at point x1 in figure. I'm studying the way in which Ansys uses the Newton-Raphson method when there are nonlinearities. In the slide ...
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
97 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 ...
0
votes
1answer
77 views

The proper way to assess the error of Jacobi iteration (for 2D Poisson equation)?

Motivation: I'm using 2D regular grid (it's actually a quadtree but I can still treat it as a finite difference thing if I weight-average the solution over smaller scale cells for the purpose of ...
2
votes
2answers
247 views

Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?

Recently, I have met a question that a saying goes that for large linear system: iterative methods are required because of memory problem of direct methods. But when I implement some experiments ...
6
votes
0answers
59 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, ...
3
votes
1answer
376 views

What's the terminology for this alternative minimization algorithm?

Say the model is $F(x_1)G(x_2)Z(x_3) = y \in \mathbb{R}^N$, with $F,G,Z$ explicitly known, we are given observation of $y$ as $y_b \in \mathbb{R}^N$ to find the value of $x_1$, $x_2$, $x_3$ for each ...
6
votes
1answer
296 views

Iterative linear solver for “ugly” saddle point system

I am a graduate student majoring scientific computing. The numeric model I made caused a very ugly-looking saddle-point linear system. It is not symmetric at all and I will attach the sparsity pattern ...
1
vote
1answer
89 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 ...

1
2 3 4 5