Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

41 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
180 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
8
votes
0answers
213 views

Wanted: sequences of linear systems for recycling Krylov solver analysis

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
7
votes
0answers
72 views

How to construct an effective preconditioner for this particular problem

A quick introduction to my problem I am currently developing a method for simulation of water waves in three dimensions based on potential flow theory. The computational bottleneck of the method is ...
6
votes
0answers
122 views

What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
5
votes
0answers
162 views

conjugate gradient for Newton's method with non positive definite Hessian matrix

I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$: $$ \...
5
votes
1answer
235 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 ...
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 ...
4
votes
0answers
195 views

Once and for all: Which FEM plattform should I use for a very large multiphysics simulation?

I'm fooling around with the decision on how to build a multiphysics simulation for too long now (also several questions in this forum). First, I thought it would be possible/necessary to write most of ...
4
votes
0answers
142 views

How big a matrix can we row reduce in reasonable time?

I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank). The good news is that I work mod 2 and the ...
3
votes
0answers
63 views

Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
3
votes
0answers
106 views

Iteratively solving a sparse, ill-conditioned system

I have a sparse (density = 0.2%), ill-conditioned system that I am trying to solve, with no luck. Background I have a sequence of sampled data, where two of every 8 samples have been zeroed due to a ...
3
votes
0answers
48 views

Preconditioning matrix with known spectrum

Assume I know all eigenvalues of a matrix $A$ fall into a certain set $\Omega \subset \mathbb{C}$. Is there any way I can exploit this knowledge to design a preconditioner for $A$? Some further ...
2
votes
0answers
68 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:...
2
votes
0answers
106 views

Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
2
votes
0answers
75 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
2
votes
0answers
164 views

Iterative linear solvers compatible with automatic differentiation?

I'm using automatic differentiation on a function that contains a sparse nonsymmetric linear system to be solved. I was using BiCGStab to solve this part of the function, but noticed the derivatives ...
2
votes
0answers
50 views

Scaling for a nonsymmetric eigenvalue problem

I have an eigenvalue problem emerging from the internal vibro-acoustic coupling. The eigenvalue problem is nonsymmetric but it was proven in literature that it results in real eigenvalues and ...
2
votes
0answers
94 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
2
votes
0answers
153 views

Fast solution of a heptadiagonal linear system

I have a linear system of the form $\mathbf{A}\mathbf{x} = \mathbf{f}$. If the length of the vector $\mathbf{x}$ is $N$, meaning that there are $N$ unknowns, then the matrix $\mathbf{A}$ has seven ...
2
votes
0answers
81 views

Solve for $D$ in $R^{T}DSDR = Id$

Given that $R$ is a rectangular matrix, $D$ is a diagonal, square matrix and $S$ being a square matrix along with the fact that both $D$ and $S$ are invertible. $S$ in this specific case can be ...
2
votes
0answers
178 views

Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?

I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
2
votes
0answers
607 views

Solving a system of 4 coupled PDEs representing variable diffusivity

I have four partial differential equations representing mass conservation of two compressible fluid phases (marked by subscripts $p1$ and $p2$) in two different continuum media (marked by subscripts $...
2
votes
0answers
93 views

Adaptive Mesh vs Uniform Mesh for multiple source/boundary/initial Data

I'm going to ask some beginners' questions. Adaptive mesh can save many DOFs than a uniform mesh. But it also needs to solve linear systems changing with mesh adaptive process. Is this not problem? ...
2
votes
0answers
119 views

Lapack++ for QR algorithm

I have recently started using Lapack++ which I found convenient for my programming purpose, in general. Now, I need to solve a matrix using QR algorithm. I've searched the user manual and I found a ...
2
votes
0answers
217 views

Is it possible to run a Solver Foundation solver against a model containing linear and non-linear elements?

This is a follow up question to one I made previously about non-linear equations and ranged real numbers in Solver Foundation. I acknowledge that where possible, rewriting a problem that is non-...
1
vote
0answers
37 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
1
vote
0answers
58 views

Why do higher order finite elements (Q2) do not perform well for large Peclet number flows, as compared to Q1 finite elments?

I a solving the 2d steady state convection-diffusion problem on the famous flow around a cylinder in rectangular domain benchmark. My numerical results show that with Q1 finite elements, the solver is ...
1
vote
0answers
58 views

Parallel dense solve with submatrices from mesh refinement with Petsc

For a Bounday Element Method problem I require the solution of a system of linear equations with multiple right-hand sides. Though this is a dense system, I still want to do it via Petsc in parallel. ...
1
vote
0answers
42 views

Iterative solver, which balances the equations with the biggest errors

I am trying to understand the mathematical side of an algorithm, which approximates the solution of coulomb's law. Their approach is to balance the two elements with the biggest positive/negative ...
1
vote
0answers
181 views

How to reshape matrix into row-major order for MKL DSS?

I would like to use MKL to solve a sparse linear system. I chose the DSS (Direct Sparse Solver) interface, which implements the following steps: ...
1
vote
0answers
86 views

QR via Householder: less computationally complex variants?

I'm a probabilist and need to do a few computations for a rather big linear least squares problem, so I'm trying to optimize the computation as far as is feasible to me. In computing the QR ...
1
vote
0answers
84 views

What does it take to prove that a multigrid algorithm scales linearly with system size?

It is my understanding that the multigrid solution techniques are generally the preferable method to solve large Poisson problems. Now assume I have written a multigrid solver that is tailored to my ...
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
118 views

Updating factorization of Laplacian (add/remove edges)

For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ...
1
vote
0answers
31 views

Difference between Chebyshev first and second degree iterative methods

Consider linear equation $Au = f$. We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree ...
1
vote
0answers
490 views

Implementation of a direct solver in Fortran 90?

My question may be elementary, but it is quite essential as I am getting confused. Here I am supposed to solve the following equation: $Ax=B$ From my understanding I have options of using either ...
1
vote
0answers
464 views

General algorithm to solve systems of symbolic equations

I want to simplify (solve) a system of linear + nonlinear symbolic equations as much as possible. the equations are of random orders, without differentiation. is there a general & well-known ...
1
vote
0answers
244 views

Memory allocation error with GSL ODE solver applied to system of 4 ODEs

I am trying to solve a (large) system of ODEs with GSL solvers. When I use driver method I get an error message of could not allocate space for gsl_interp_accel, ...
0
votes
1answer
72 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?
0
votes
0answers
68 views

Algebraic multigrid for coupled equations

As far as I understand is algebraic multigrid(AMG) a method that was intentionally developed to solve linear systems where every grid point or node has a single DOF. When AMG should now be used for ...
0
votes
0answers
582 views

Tridiagonal Solver in Python

I have a code I'm working on that involves solving a 1D Schrodinger equation using a Crank-Nicolson time step. The code is written in NumPy/SciPy, and I was doing a bit of profiling and discovered ...