Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
2 votes
0 answers
127 views

Plasma charge conservation for a multi-Euler system - looking for quasi-linear Riemann solver that also resolves slow contact discontinuity

I am solving a multi-species plasma problem by assigning a set of ideal gas Euler equations to each species, e.g. protons and electrons. I.e. I am solving the system $$ \partial_tU_s + \partial_x(F_s) ...
AtmosphericPrisonEscape's user avatar
7 votes
3 answers
1k views

How large is large for direct solvers?

Let us say I want to solve a large sparse linear system. It is said that iterative solvers should be better than direct solvers in this case. But how large is large? What is the exact threshold beyond ...
timur's user avatar
  • 181
5 votes
2 answers
127 views

Cheap way to keep parameter matrices orthogonal during optimization?

TLDR; I can keep matrix variables approximately orthogonal by taking a single gradient step in the direction of "effective rank" of matrix at each step of iterative solver, is there a more ...
Yaroslav Bulatov's user avatar
0 votes
1 answer
67 views

Weird runtime behavior of `scipy.linalg.solve_triangular` and `trtrs`

I want to understand the time complexity of scipy.linalg.solve_triangular, which calls trtrs from LAPACK under the hood, so I ...
nalzok's user avatar
  • 181
4 votes
1 answer
228 views

Saddle point system

I am solving a system of the form $$ \begin{pmatrix} A & b^T \\ b & 0 \end{pmatrix} \begin{pmatrix} x \\ \ell \end{pmatrix} = \begin{pmatrix} c\\ 0 \end{pmatrix} $$ Where $A$ is a symmetric ...
Beni Bogosel's user avatar
  • 1,037
0 votes
0 answers
31 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
0 answers
148 views

Population of the coefficient matrix of a linear system Ax=b stemming from the finite differences of an arbitrary geometry

I've been looking into solving a linear system $$Ax=b$$ where $A\in\mathbb{R}$ is the sparse coefficient matrix of size $K\times K$, $b\in\mathbb{R}$ is the right-hand side (i.e., the source term) of ...
Akhaim's user avatar
  • 83
0 votes
0 answers
59 views

Solving AU = F using linalg.cg results in 0 iterations

I am working on solving the following PDE: $$\left(\mu_{x}\frac{\partial^{2}u}{\partial x^{2}}+\mu_{y}\frac{\partial^{2}u}{\partial y^{2}}\right)=f(x,y) \tag 1$$ Which is then discretised: $$- \mu_{x} ...
blov's user avatar
  • 43
2 votes
1 answer
59 views

Solving $(I-Q)x={\bf 1}$ for sub-stochastic sparse $Q$ of dimension 5M $\times$ 5M

I have a (right) sub-stochastic CSC sparse matrix $Q$ of dimension 5 million, with 200 million nonzero entries, which is a nonzero percentage of 0.0008%, so it is indeed extremely sparse. It is not ...
Set's user avatar
  • 503
2 votes
1 answer
81 views

Solving for $X$ in $\sum_{a,b} b a^T b^T X a = Y$

Suppose I have $k$ pairs of $(a,b)$ where $a$ and $b$ are vectors in $\mathbb{R}^d$, $Y$ is $d\times d$ and I need least squares solution for $X$ in the following $$\sum_{(a,b)}^k b a^T (b^T X a) = Y$...
Yaroslav Bulatov's user avatar
2 votes
0 answers
42 views

How to use a preconditioner estimated from a subset of data?

Suppose I'm solving $Ax=b$ using row-action method like Kaczmarz for $m\times n$ matrix A with $m\approx \infty$ and have $H_k=\frac{1}{k}A_k^T A_k$ which is an estimate of the Hessian obtained from ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
211 views

Right blocked linear equation solver on Dense Algebra and Sparse Algebra

I have implemented 1D mesh parallel QR decomposition and LU decomposition,I would like to ask if a linear equation Ax=b,b is a large matrix and I need to shard b or Shard A,b at the same time. Is ...
Haitao Xiao's user avatar
5 votes
1 answer
98 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
1 vote
0 answers
60 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
  • 11
2 votes
2 answers
476 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
  • 333
0 votes
0 answers
46 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
  • 193
1 vote
2 answers
156 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
54 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
1k 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
171 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
61 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
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
1 vote
0 answers
110 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
  • 259
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
46 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
268 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
74 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
35 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
66 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
627 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
73 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
  • 189
3 votes
1 answer
227 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
256 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
  • 362
4 votes
0 answers
134 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
68 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
  • 607
5 votes
0 answers
197 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
2 votes
0 answers
44 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
  • 2,112
0 votes
0 answers
67 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
  • 362
0 votes
1 answer
2k 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
1 vote
2 answers
79 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,112
2 votes
0 answers
46 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
140 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
296 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
98 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
102 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
551 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,112
2 votes
0 answers
116 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
586 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,037
1 vote
1 answer
986 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 ...
user avatar

1
2 3 4 5
9