Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
391
questions
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 ...
- 141
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 ...
- 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 ...
- 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 ...
- 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 ...
- 111
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....
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 ...
- 121
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$...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 2,049
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$, ...
- 2,049
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 ...
- 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 ...
- 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 ...
- 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_{...
- 21
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 \...
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 ...
- 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 ...
- 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 ...
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 ...
- 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-...
- 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 ...
- 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&...
- 2,049
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 ...
- 971
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.
...
- 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$ ...
- 11
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 ...
- 971
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 ...
- 183
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 ...
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 ...
- 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 ...
- 3,263
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 ...
- 21
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 ...
- 971
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 ...
- 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 ...
- 985
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 ...
- 201
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 ...
- 201
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}$. $\...
- 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.
\...
- 111
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 ...
- 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(...
- 91
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 \...
- 1,074
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$)...
- 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 ...
- 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, ...
- 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 ...
- 41
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 ...
- 11.2k
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 ...
- 1,463