Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
4 votes
0 answers
59 views

Computational efficiency of Galerkin projection in AMG

I have been using recently AMG as preconditioner for CG with several meshes for simple elliptic problems discretised with linear elements on "complicated" three dimensional geometries and I ...
FEGirl's user avatar
  • 405
1 vote
0 answers
106 views

Iterative PDE solver for 1D Burgers equation

I am looking for an Iterative Numerical PDE solver for 1D Burgers equation. I need to have access to the intermediate solutions of the Numerical Solver. By iterative methods, I mean techniques which ...
rajoy99's user avatar
  • 11
0 votes
0 answers
103 views

Is there a fast matrix-free inverse power iteration?

Problem: I want to solve the eigenvalue problem $$x=Ax$$ to the eigenvalue $1$ for a large matrix (roughly $N^3\times N^3$ and $N$ ranges from 10 to 100) where $A$ is stochastic (i.e. all entries are ...
Diplodokus's user avatar
0 votes
0 answers
37 views

Flexible Conjugate Residual

If we want to use variable preconditioning in Conjugate Gradient, we can replace the Fletcher–Reeves by the Polak–Ribière formula (https://en.wikipedia.org/wiki/Conjugate_gradient_method#...
GS101's user avatar
  • 21
3 votes
1 answer
210 views

Iterative solver for high order DG methods (3D Laplace problem)

I have a 3D Laplace problem on quite a complicated geometry where I am using Discontinuous Galerkin method. My mesh is composed by hexas, hence I am employing classical tensor product basis functions $...
FEGirl's user avatar
  • 405
0 votes
0 answers
33 views

How conservation of momentum is ensured in (Projected) Gauss-Seidel constrain solver

I'm developing molecular dynamics where my time-step is limited by stiffness of the bonds. I trying to get inspiration from game-engines, where they solve similar problem (hard bond constrains). These ...
Prokop Hapala's user avatar
3 votes
1 answer
167 views

Approximately, at any given time, what proportion of the world's total HPC resources are dedicated towards inverting matrices?

I had heard in a lecture, perhaps 15 years ago, that the vast majority of the world's HPC resources were dedicated to solving linear systems by iterative methods. I seem to remember it was 90%. I can'...
djps's user avatar
  • 31
1 vote
2 answers
103 views

Implementing matrix term version of Gauss-seidel

I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
Jared Frazier's user avatar
3 votes
0 answers
114 views

Stochastic power iteration for generalized eigenvalue problems?

Suppose $\mathbf{x}$ is a random variable in $n$ dimensions, and $u$ is a vector. How can I estimate the following quantity in an online fashion? $$f(x)=\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
Yaroslav Bulatov's user avatar
0 votes
1 answer
89 views

How can I find the current for a nonlinear electrical circuit using the Shockley equation, in Octave?

For this electrical circuit: The voltage $ V_D $ can be found by solving a nonlinear equation: $$ \frac{V_{DD}}{R} - \frac{V_D}{R} - I_se^{V_D/V_T} = 0 $$ In this example, let $R=1000$, $V_T = 0.025$,...
Astor Florida's user avatar
2 votes
2 answers
479 views

Iteration counts of AMG solver changes in parallel

I am solving the linear elasticity equation within a FEM library with a complex 3D geometry. The resulting linear system is solved with CG, preconditioned by AMG (Algebraic Multigrid). The computed ...
FEGirl's user avatar
  • 405
0 votes
0 answers
117 views

Algorithm to solve system of nonlinear equations

I would like some tips in figuring out a good algorithm to find the solution of the following system. Let $\theta$ be a constant in $(0,1)$, let $i,l=1,...,N$, let $a_{l}$ and $b_{i,l}$ be some ...
Andres's user avatar
  • 1
0 votes
0 answers
38 views

Equilibrium position finding with DSM

I've coded a framework that can be used to simulate the dynamic behavior of a system discretized by particles (nodes) that are connected by spring-damper elements. However, I want to compare it to a ...
AlexBatch's user avatar
0 votes
0 answers
50 views

Professional orbital simulation software methods, accuracy, runtime

I'm working on an orbital body simulation as a personal project. I understand that it's not going to be as good as professional software, but I'm wondering what contemporary, general purpose, ...
Indrada's user avatar
4 votes
1 answer
162 views

Is there a way to generate a matrix-free decomposition for a matrix-free operator?

Hypothetical question for some code that I'm writing. Suppose I have an matrix-free linear operator $A$, i.e. the only thing I know about it is the forward action $v \mapsto Av$. For simplicity, let's ...
TrostAft's user avatar
  • 141
0 votes
0 answers
66 views

Compatibility condition for Poisson equation in cylindrical symmetry

I'm trying to implement multigrid approach for a Poisson equation $\frac{1}{r}\frac{\partial}{\partial r}\left( r \frac{\partial H}{\partial r} \right) = f$ with all Neumann boundary conditions. ...
Yakovenko Ivan's user avatar
2 votes
1 answer
175 views

Solution of linear system doesn't work, in parallel

I'm solving $Ax = b$ with PETSc, $A$ sparse and asymmetric. I'm using BCGS or FGMRES or TFQMR as a solver, and ILU as a preconditioner. When I use 1 core, everything works as expected. But with 8 ...
Lilla's user avatar
  • 259
2 votes
0 answers
133 views

Does exact diagonalization of a matrix allow for efficient computation of a Lanczos basis?

Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the ...
miggle's user avatar
  • 41
1 vote
1 answer
83 views

Powers of convergent DPR1 matrices in $O(d)$ time?

Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix. How do I estimate $u^T A^k v$ in $O(d)$ time? Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
Yaroslav Bulatov's user avatar
1 vote
0 answers
119 views

Which dense matrices are hard to invert?

Suppose I'm solving $Ax=b$ for dense $m\times d$ matrix $A$. For which $A$ is this hard to do? More concretely, is there any work on estimating the error after $k$ steps of iterative solver, $k\le d$, ...
Yaroslav Bulatov's user avatar
1 vote
0 answers
62 views

Does the choice of a complex inner product affect Krylov methods?

As far as I understand there are two definitions of the complex inner product: $$(a,b) = b^H a$$ and $$(a,b) = a^H b$$ I know some linear algebra libraries such as BLAS and Eigen uses the second one. ...
Alexandre Hoffmann's user avatar
0 votes
1 answer
204 views

Can successive over-relaxation (SOR) method deal with ill-posed PDE BVP?

Recently, I've been struggling to understand the limitations and capabilities of the successive over-relaxation (SOR) method for boundary value problems which are ill-posed, such as, for instance, ...
Akhaim's user avatar
  • 83
1 vote
1 answer
289 views

Convergence stall when solving 2D Poisson PDE with pure Neumann boundaries (finite differences)

I recently started coding a small library of 2D PDE solvers (time dependent and time independent), and my first attempt was a 2D Poisson equation of the form: $$\nabla(\epsilon\nabla\varphi)=\nabla\...
Akhaim's user avatar
  • 83
3 votes
3 answers
174 views

How to find the optimal SSOR parameter

The symmetric successive overrelaxation method features the iteration matrix $$P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+U\right)$$ Either as a stationary ...
shuhalo's user avatar
  • 3,670
1 vote
0 answers
39 views

Solution to minimization problem when variables factor in 2 analytical problems

I am asking a follow up question to this question, but I could probably have written it as an answer instead. However, I don't know if what I am doing here makes sense or is too complicated for my ...
PC1's user avatar
  • 436
2 votes
1 answer
112 views

Iterative solution for a minimization problem involving matrix equations

I have a real valued function $F$ for which I am looking to find its global minimum. The function is well behaved and I can obtain its Jacobian. I could also compute the Hessian but the function ...
PC1's user avatar
  • 436
5 votes
2 answers
437 views

Recurrence relation for matrices

I have matrices ($S_0$ thought $S_N$) and I have a recurrence relation that link successive matrices together. $$S_i + S_i(aS_{i-1}^{-1})S_i=C_i+aS_{i+1}$$ We can assume for this problem that $S_0=S_N=...
PC1's user avatar
  • 436
0 votes
2 answers
122 views

Eigenvectors of Laplacian

I am studying introduction to Multigrid methods. In all tutorials, authors write that eigenvectors of Laplacian (1D, finite difference) are given as $w_k(x_i) = \sin(k \pi x_i),$ where $x_i$ is a ...
student1's user avatar
1 vote
1 answer
83 views

Memory issues with iterative solvers

Was trying to implement a poisson 2d solver using Conjugate Gradient Method, so from 10x10 grid the matrix becomes 100x100 (since we have 100 nodes to find the values at), 100x100 grid goes to ...
2Napasa's user avatar
  • 362
3 votes
1 answer
1k views

Solving Kepler's Equation with Newton-Raphson Method

Note (2022/03/07): This question is solved. Unfortunately, I'm not able to accept the correct answer by Lutz Lehmann, because I screwed up my registration and the account which posted this question is ...
kruemelkeksfan's user avatar
2 votes
2 answers
96 views

Possible to use Iterative FD methods to solve a transformed non square domain [matlab]?

For the 2-D Poisson equation $$-(u_{xx}+u_{yy}) = f \ \ \text{where} f = 1$$ For boundary conditions $$\frac{\partial u}{\partial n} = 0 \ \text{on AB and AD}$$ $$ u = 0 \ \ \ \text{on BC and CD no-...
bc_eng's user avatar
  • 23
1 vote
0 answers
73 views

Slow convergence of Stokes solver used with the Immersed Boundary method

I am using Immersed Boundary Method to simulate elastic particles in 3D Stokes flow. Specifically, one has $\nabla ^2 \mathbf{u}-\nabla p + \mathbf{f}(t) = 0$, $\nabla \cdot \mathbf{u} \; $, where $\...
P. Trinli's user avatar
3 votes
0 answers
51 views

Pass forward intermediate results during iterative optimization

To investigate a counter-current flow heat exchanger while considering temperature dependent physical properties (such as specific heat $c_\textrm{p,i}$, heat conductivity $\lambda_\textrm{i}$, ...
albert's user avatar
  • 203
3 votes
1 answer
584 views

Incomplete Cholesky preconditioner for CG efficiency

I am currently solving the harmonic equation using a P1 FEM discretisation. The resulting matrix $A$ is SPD and fairly sparse so I use a preconditioned conjugate gradients (CG) solver to find a ...
lightxbulb's user avatar
  • 2,162
3 votes
1 answer
628 views

When do not use preconditioners for sparse linear system of equations?

I'm implementing a solver of Finite Element Method, and to solve the linear system of equations I'm using gmres from MKL of Intel. Exists the option with and without a preconditioning. In what case it ...
yemino's user avatar
  • 515
0 votes
0 answers
99 views

Help with debugging block GMRES

I have written block version of GMRES by referring [1] and MATLAB implementation of gmres. I need to write it for complex matrices. My block implementation when run on single RHS is giving correct ...
anantdevi's user avatar
6 votes
2 answers
153 views

Integrating exponential of second degree polynomials

I'm looking to compute the value of the following integral, for small values of $|a|$. $$u_n(a,b)=\frac{1}{2}\int_{-1}^1 x^ne^{ax^2+bx}\mathrm{d}x$$ In this equation, $a,b \in \mathbb{R}$ and $n \in \...
PC1's user avatar
  • 436
3 votes
1 answer
405 views

Doubt regarding GMRES(m) and preconditioned GMRES

I have the two following algorithms for GMRES(m) and left preconditioned GMRES. GMRES(m) Left preconditioning I would like to know if anyone could explain why steps 10 through 12 are not used in the ...
user avatar
1 vote
1 answer
32 views

Find best matching ranges below limit in defined set of numbers

I am trying to calculate the best set of cuts for some wood cutting to reduce the waste. So: Given a set of numbers, the goal is to find the best matches below a limit (size of wood beam). Example of ...
kaiser's user avatar
  • 111
4 votes
1 answer
145 views

Solving for a single element of a solution of a linear system

I wish to solve a linear system $A x =b$ in which $A$ is dense but not too large, say no larger than $10\times10$. However, I am not interested in the full solution vector $x = [x_0, x_1, \dots]$, ...
Endulum's user avatar
  • 735
4 votes
0 answers
195 views

Stable iterative solver for complex symmetric linear systems

I am interested in the iterative solution (preferably Krylov-type solvers) of a problem $\boldsymbol{A}x=b$, with $x,b\in\mathbb{C}^{n\times1}$ and $\boldsymbol{A}\in\mathbb{C}^{n\times n}$. $\...
Breno's user avatar
  • 141
2 votes
1 answer
59 views

Simulate circular mold spread using cellular automata - square emerges instead

I am trying to simulate the spread of mold in a petri dish using a cellular automata based approach. Thanks to the answer in my other question Stochastic cellular automata - algorithm limited by 1 ...
Seth Lutske's user avatar
4 votes
1 answer
109 views

Stochastic cellular automata - algorithm limited by 1 cell per timestep

Context Let's say I am trying to model the spread of mold in a petri dish, using a stochastic cellular automata approach. The petri dish can be thought of as a grid of 1mm x 1mm squares, each called ...
Seth Lutske's user avatar
0 votes
1 answer
197 views

Best search algorithm for optimal weight factor in SOR method

I had written an algorithm that searches for the optimal weight parameter to be implemented in the successive-over relaxation (SOR) method which worked cleanly by vectorizing the interval and for ...
SPARSE's user avatar
  • 169
3 votes
0 answers
213 views

How to obtain smallest eigenvalues with Arnoldi iteration

I understand that the Arnoldi iteration produces a basis which tends to include in its span the eigenvectors corresponding to eigenvalues of large magnitude (hence the analogy between the last vector ...
Pedro Secchi's user avatar
-1 votes
1 answer
57 views

relres in gmres MATLAB

I think the relres in MATLABis the form that relres = norm(M(b-Ax))/norm(M\b),when it smaller than tol then stop the iteration. I want to know how to change relres to norm((b-Ax))/norm(b). Or use ...
aouii's user avatar
  • 1
7 votes
2 answers
255 views

solving linear system whose symmetrized matrix is positive definite

Are there iterative methods for the solution of nonsymmetric linear systems $Ax=b$ that can take (theoretical or practical) advantage from knowing that $A+A^T$ is positive definite? These matrices are ...
Arnold Neumaier's user avatar
0 votes
2 answers
345 views

Why minimizing with respect to A-norm?

Assume solving the linear system $A \textbf x = \textbf b$, with an $A$ so large that nothing but iterative methods may be employed. Assuming $A$ induces a norm, I realized that it is often desired to ...
arash's user avatar
  • 21
1 vote
0 answers
37 views

Approximation in the derivation of the Arc Length method

I am studying the proof of the Arc Length method in section 2.2 of this thesis. In equation (2.2) the author introduces the supplementary conditions $$ (\Delta {\bf u} + \delta {\bf u})^T \cdot (\...
Olumide's user avatar
  • 275
3 votes
0 answers
157 views

Python routine to calculate shape resonances of H2

I am currently doing a project in which my aim is to write a program that can be used to calculate single and multi-channel shape resonances. So I'm looking at bound states and quasi-bound states. ...
Alon Shoshan's user avatar

1
2 3 4 5
7