Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
4 votes
1 answer
40 views

Updating QR decomposition for geometrically similar least squares problem

Let's say we have a weighted least squares problem under the same matrix $A$ such that, $$\hat{x} := \arg \min_x ||A x - b||_{W_1}$$ where $|| \cdot ||_{W_1}$ is the Euclidean norm weighted by ...
Nicholas Mancuso's user avatar
0 votes
0 answers
16 views

preconditioning least square in python?

For a nonsymmetric matrix, we can solve { A^T @ A x = A^T b } by lsqr or cgls or something else. Usually it will be slow, so we need a preconditioner either ilu, multigrid or something else. Is there ...
Alvin's user avatar
  • 1
2 votes
2 answers
434 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
  • 261
0 votes
0 answers
37 views

recommendation on some papers/books about frontal solver used in FEM

I'm reading a program about computational plasticity, this program use frontal solver to solve the program, but I'm not familiar with frontal solver even after reading some papaers, so could you ...
吴yuer's user avatar
  • 21
1 vote
2 answers
104 views

Are there good block sparse matrix solver libraries?

There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries. However, often in optimization ...
user664303's user avatar
0 votes
0 answers
43 views

How do compute lowest eigenvalue using Arpack in C language

Hi I have a problem to calculate lowest eigenvalue in non-symmetric matrix using Arpack, because my matrix is very complicated and even I have a lot of trouble to made a matrix - vector multiplication....
Maciej Lewkowicz's user avatar
11 votes
1 answer
981 views

Is using iterative methods to solve a linear system always superior to inversing the matrix?

I have a silly question. Is it always more computationally efficient to use iterative methods to solve for some matrix $A$, $Ax=b$, where $x$ and $b$ change but $A$ stays constant, compared to ...
Touko Puro's user avatar
2 votes
1 answer
167 views

Numerically stable way to implement Cramer's rule analog

Problem statement Let $A$ be an $n\times n$ matrix and $b$ an $n$-dimensional vector. For $j\in \{1, \dots, n \}$, let $A_j$ be the matrix where we take $A$ and replace the $j^{\rm th}$ column with $b$...
Joe's user avatar
  • 31
0 votes
1 answer
56 views

Reverse engineering phase shift and numerical damping

I've been trying to validate the physics behind a particle system framework, but I'm having some difficulties. A particle system is a set of lumped masses connected by spring-damper elements. Linear ...
AlexBatch's user avatar
2 votes
1 answer
171 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 ...
hahn76's user avatar
  • 243
2 votes
0 answers
97 views

Schur complement formulation of linear system

Consider a system of the following form: $$(A+K)x=b$$ where $A$ is symmetric, positive definite and block diagonal (in fact, a block diagonal matrix made of stiffness matrices arising from FEM ...
Lilla's user avatar
  • 127
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
114 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
43 views

FEM Basis for functions of two variables in $\mathbb{R}^2$ (Applied to Linear Full Stokes Equations)

I'm trying to do FEM for a very basic version of the linear full Stokes equations in two dimensions. Say we are working in the grid $[0,1]\times[0,1]$ in the $xy-$plane. To solve an FEM problem for a ...
k12345's user avatar
  • 111
5 votes
1 answer
170 views

Block-Tridiagonal Matrices with tridiagonal blocks

The Setup Using finite differences to discretize the 2d diffusion equation $$\partial_tu=\partial_x\left(A\partial_xu+B\partial_yu\right)+\partial_y\left(B\partial_xu+C\partial_yu\right)$$ we get a ...
Michael's user avatar
  • 153
0 votes
1 answer
57 views

How to combine multigrid preconditioner with jacobi preconditioner?

I have not found any relevant information in the literature on the following rather simple problem: How to combine (geometric) multigrid preconditioned conjugate gradient (MGPCG) with an additional ...
zx-81's user avatar
  • 1
2 votes
0 answers
34 views

How to exploit QR factorization implicitly

I meet a problem when I try to develop an iterative method for discrete inverse problem $$Ax+e=b$$ where $A\in\mathbb{R}^{m\times n}$ and $e$ is a noise. I want to approximate the true solution $x_{...
Haibolee's user avatar
0 votes
1 answer
63 views

Solving a linear system whose coefficient matrix is dense but symmetric

For solving a linear system, $Ax = b$. If $A$ is a dense but symmetric $n \times n$ matrix, how much memory is required? $A$ is symmetric, which means only the upper (or lower) triangular part of $n \...
Yonghyun Chung's user avatar
2 votes
1 answer
344 views

How to extract intermediate calculation results from an SciPy ODE function in python?

I have a bit lengthier ODE function which was simulated by using Scipy solve_ivp function. During this simulation I calculated many parameters but as the output, I am taking out put only some other ...
Nis's user avatar
  • 21
1 vote
1 answer
72 views

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

In passing I was told by someone that $K^{\prime}\in\mathbb{R}^{n\times n}$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $K$, where $K$ is ...
Tucker's user avatar
  • 159
3 votes
1 answer
226 views

Correctness of direct numerical solution of ill-conditioned linear system

To what extent can you put trust in a numerical solution obtained by direct solver for an ill-conditioned linear system? In other words, how can you test the solution? Dropping it into the system says ...
Fidel Pestrukhine's user avatar
3 votes
1 answer
200 views

BiCGSTAB convergence

So I need a fast converging solver for SysLinEq as a subroutine in fortran, decided to test BiCGStab in Matlab. Thank God I decided to test it out on first before implementing in Fortran as a ...
2Napasa's user avatar
  • 364
4 votes
0 answers
130 views

How does one proceed to solve (big) underdetermined or overdetermined systems of linear equations "nowadays"?

In my numerical linear algebra class we mentioned this problem briefly and according to some other lectures on the internet especially in data driven environments one mostly has to deal with such over-...
Sen90's user avatar
  • 141
3 votes
0 answers
63 views

Dense factorization specialized for RBF-FD method

In RBF-FD methods (see Fornberg & Flyer. A Primer on Radial Basis Functions with Application to the Geosciences. SIAM, 2015. Chapter 5.), the finite-difference stencil coefficients for a set of ...
IPribec's user avatar
  • 454
5 votes
0 answers
187 views

Dense least-squares with millions of variables

Suppose $X$ is a dense $m\times n$ data matrix and we seek to find $w$ by approximately iterating least-squares filter equation: $$w = w - \mu (X'X)^{-1}X'(Xw-b)$$ What are known approaches for $10^9&...
Yaroslav Bulatov's user avatar
1 vote
0 answers
41 views

Iterative methods for underestimate of smallest eigenvalue for large sparse matrices

I recently read the paper "EUCLIDEAN-NORM ERROR BOUNDS FOR SYMMLQ AND CG" by Estrin et al. and there they use an underestimate (i.e. something in $(0,\lambda_{min}]$) of the smallest ...
lightxbulb's user avatar
0 votes
0 answers
66 views

Passing boundary conditions to solver

Quite broad question, Currently building own Poisson solver subroutine for CFD solver. Works smooth, the goal is to generalise the input and make it flexible. Description of also: Memory allocation. ...
2Napasa's user avatar
  • 364
0 votes
1 answer
876 views

Solve a large-scale linear system of equations with millions of unknowns

I have a large-scale system of linear equations: $Ax = b$, where $A$ is an $n\times n$ square symmetric positive definite matrix (not sparse), $b$ is an $n \times 1$ vector and $x$ is $n\times 1$ ...
Math_Lover's user avatar
0 votes
2 answers
76 views

Solvers for odd order PDE finite difference discretisation

I am used to solving elliptic PDEs of even order. I was wondering what would one do for odd order PDEs. Notably the discretisations of those results in unsymmetric matrices. I tried solving the ...
lightxbulb's user avatar
2 votes
0 answers
45 views

Solving linear system and obtaining operator norm

I need to solve a linear system of the form $(\mathrm{Id} + \mathbf{J})\mathbf{x} = \mathbf{b}$ for $\mathbf{x}$ and I also need to compute the operator norm of $\mathbf{J}$ (i.e. the largest singular ...
5d41402abc4's user avatar
1 vote
1 answer
125 views

Sparse direct solver that works inside opened omp parellel region?

Does anyone know a library that implements sparse direct solver working in already open omp parallel region? The only library that I know that works with this requirement is Pardiso7.2 worth ~8K USD ...
Cesar Conopoima's user avatar
0 votes
0 answers
255 views

Solving huge dense square symmetric linear system

I have a linear system of the type $A x = y$ where A is a dense, square, symmetric, positive definite matrix, $x$ a vector of unknown parameters, and $y$ is a vector of observed quantity. I know that ...
pinpon's user avatar
  • 153
4 votes
0 answers
85 views

Comparing block versus non-block Krylov methods for handling multiple right-hand-sides

Suppose I wish to solve a linear system $AX=B$ iteratively where $A$ is an $m\times m$ matrix and $X,B$ are $m \times s $ matrices (not single vectors). Instead of solving $s$ independent systems I'm ...
Reid.Atcheson's user avatar
1 vote
1 answer
97 views

Elementary question on numerical linear algebra

I’ve been facing a problem of solving linear systems Ax=b arising from discretized PDEs (Stokes equations in particular). Nively, it seems that solving Ax=b should not take much more time than simply ...
P. Trinli's user avatar
3 votes
1 answer
401 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 votes
0 answers
105 views

Regularisation of ill-conditioned matrix-vector problem

I have a linear* problem which arises from an integro-differential system, and writes: $$ (\mathbf{I}+\lambda \mathbf{A})x = b $$ where $\mathbf{A}$ is a real full matrix, size $n\times n$, but is not ...
Joce's user avatar
  • 362
2 votes
2 answers
502 views

Different sources of error in Finite Element computations

Consider the problem $-\Delta u = f$ in $\Omega$, with $u=0$ on $\partial \Omega$. Suppose that $\Omega$ is a polygon and that we approximate the solutions to the previous problem using Lagrange ...
Beni Bogosel's user avatar
1 vote
1 answer
845 views

Givens rotation algorithm without matrix-matrix multiplication

I would like to implement a givenRotation algorithm without having matrix-matrix multiplication. Matrix-vector is fine or just for looping. I am to decompose a rectangular (m+1)xm Hessenberg matrix. I ...
Manuel Oliveira's user avatar
3 votes
1 answer
303 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 ...
Manuel Oliveira's user avatar
4 votes
0 answers
174 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
5 votes
1 answer
170 views

Solving absolute value systems

Let $z, b \in \mathbb R^n$, $A \in M_n (\mathbb R)$ and $|z| := (|z_1|, \dots, |z_n|)$. I am searching for an efficient algorithm to solve the absolute value system: \begin{equation} z - A |z| = b. \...
avril_14th's user avatar
4 votes
0 answers
149 views

Solving multiple linear regression in parallel

I am working on a problem where I need to solve approximately 500 Million Linear Regressions (OLS). What would be the most efficient way to do this (e.g. using GPU or a some framework that can do this ...
runtime's user avatar
  • 41
1 vote
0 answers
59 views

Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure

I am trying to use Newton's method to get a stationary solution for a system of equations of the following form: $$ \begin{Bmatrix} \frac{\partial x}{\partial t} \\ 0 \end{Bmatrix} = \begin{Bmatrix} f(...
Pedro Secchi's user avatar
0 votes
1 answer
104 views

Efficient solution to linear system involving Kronecker sum in MATLAB

High dimensional finite difference problems often lead to linear systems of the form $$ A x = b, \qquad A = B_1 \oplus B_2 \oplus \cdots \oplus B_d, $$ where $\oplus$ denotes the Kronecker sum. $B_i \...
Steven Roberts's user avatar
1 vote
1 answer
121 views

RCM better than Nested dissection? (For FEM discretizations in 2D and 3D)

I realize this might be a too general question but here goes nothing: I am trying different re-ordering strategies and checking the fill-in of $A=LU$. I have 2D ($p=1$, $h=1/40$ on $\Omega = [-1,1]^2$)...
bobo's user avatar
  • 91
0 votes
0 answers
63 views

Equivalence between zero sum games and linear program

It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the ...
asdf's user avatar
  • 131
4 votes
2 answers
428 views

Getting to know about various BLAS implementations

I keep coming across phrases like "highly optimized BLAS kernels" with "architecture-specific optimizations", but have never been able to find what exactly these optimizations are, ...
loonatick's user avatar
  • 151
4 votes
0 answers
201 views

hardware agnostic (GPU/CPU) sparse linear algebra C++ solvers framework/technology

I am looking for recommendations on matured C++ solver for Linear Sparse Algebra problems. The goal is to select between more or less GPU hardware agnostic libraries/frameworks that can be compiled on ...
PeterKay's user avatar
7 votes
2 answers
220 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
105 views

Simplest solver for linear equation systems

Normally, this boards sees a lot of traffic about the most efficient and most powerful solvers for huge linear equation systems. But this time, I have the opposite problem: I need to implement a ...
Michael's user avatar
  • 1,463

1
2 3 4 5
8