Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
368
questions
3
votes
0
answers
22
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 ...
- 187
5
votes
0
answers
93
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&...
- 1,124
1
vote
0
answers
33
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 ...
- 349
0
votes
0
answers
56
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.
...
- 326
0
votes
1
answer
163
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
64
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 ...
- 349
2
votes
0
answers
42
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
90
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
170
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 ...
- 121
3
votes
0
answers
67
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,203
1
vote
1
answer
91
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 ...
- 11
3
votes
1
answer
176
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 ...
- 349
2
votes
0
answers
97
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 ...
2
votes
2
answers
265
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 ...
- 965
0
votes
0
answers
45
views
Normalizing the right-hand side in Jacobi-preconditioned conjugate gradients
I have been reading the following paper: CG versus MINRES: An empirical comparison.
In it a conjugate gradient solver is applied to a system matrix $A$ Jacobi-preconditioned on both sides. ...
- 349
1
vote
1
answer
333
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 ...
- 181
2
votes
1
answer
173
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 ...
- 181
4
votes
0
answers
125
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
140
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
71
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
53
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(...
- 81
0
votes
1
answer
57
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 \...
- 934
1
vote
1
answer
92
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$)...
- 81
0
votes
0
answers
54
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
305
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
112
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
178
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.1k
0
votes
2
answers
95
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,443
2
votes
3
answers
173
views
Linear solver recommendation(s) for small problems
I am interested in solving many linear systems $Ax = b$, where $A$ is symmetric positive definite and small (i.e. less than 25,000 rows) --- $b$ will be changing.
We can assume that $A$ arises from ...
- 547
-1
votes
1
answer
96
views
Is there an overview of the runtime speed up of LP/MIP solvers throughout the years?
whenever I read papers on OR that use an LP/MIP approach, they include the time solver used, as well as the version and the year. I would like to know how much faster the same experiment would be ...
- 1
3
votes
1
answer
216
views
Preconditioning vs. regularization
I used to be more of a numerical linear algebra and computational science person, but recently, I've crossed into stats and machine learning.
For this discussion, let's focus on matrices that are not ...
- 281
-1
votes
1
answer
104
views
Combinatorial Optimization Problem with Constraints
To explain my problem I'd like to go with an example first.
Suppose I have many bills of grocery purchases in the same shop. On the invoices I can only see the total amount of the invoice and which ...
- 101
0
votes
1
answer
89
views
Solve for large array of PD matrices
I have N matrices that are positive definite, and I have to solve for a M vectors.
As M is large in my case, doing all solves simultaneously using np.linalg.solve ...
- 109
1
vote
1
answer
80
views
Algebraic multigrid as solver and as preconditioner
My question is around the efficiency of AMG. In which case AMG can perform better,as solver or as a preconditioner(for example a Krylov space method as CG)? Assume the case of elliptic pdes.
- 471
5
votes
1
answer
200
views
Solving PDEs in parallel
I have read different approaches on how to solve pdes in parallel which are discretized using finite element method. For example:
Non-overlapping domain decomposition approach as mentioned in https://...
- 471
-1
votes
1
answer
40
views
Automatic selection of the SLE solver and preconditioner during simulation
To simulate the physical process necessary to solve the arising systems of linear algebraic equations. The SLE matrix has a highly sparse form. There are a couple dozen non-zero elements in the string,...
2
votes
0
answers
42
views
"black box" preconditioner for shifted linear systems?
Does anyone know of any strategies for creating a preconditioner $P^{-1}_\sigma \approx (A+\sigma I)^{-1}$ given a preconditioner $P^{-1} \approx A^{-1}$, preferably such that the precomputation doesn'...
- 233
3
votes
0
answers
71
views
Kronecker-factored least-squares?
Suppose $a_i,b_i$ are $d\times 1$ matrices, $y_i$ is scalar, and I need to find least-squares solution $w$ of the following system of $n$ equations:
$$y_i=(a_i^T\otimes b_i^T)w$$
Is there a ...
- 1,124
1
vote
1
answer
125
views
Complexity of solving an image differential linear system
Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
- 255
6
votes
1
answer
208
views
Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$
I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
- 63
1
vote
0
answers
121
views
performance comparison between PETSc and SLATE
We want to start a new project to solve a large-scale inverse problem (O(10^6) number of parameters) to invert for subsurface wave speeds. We will use FEM to solve forward and adjoint PDEs. In our ...
- 19
3
votes
1
answer
161
views
Choice of iterative solver for a sparse asymmetric matrix with symmetric structure
I have a sparse $nxn$ matrix A with pretty interesting structure. It has a block structure with symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{kj}$ but $A_{...
- 1,902
1
vote
0
answers
76
views
Convergence of Conjugate Gradient Algorithm
I am trying to solve a linear elasticity model using finite element discretization in a rectangle domain [0,1]x[0,1]. For the solution of the the linear system $Ku=F$ I am using the CG algorithm. ...
- 471
0
votes
0
answers
49
views
Open-source iterative solvers robust to noise?
I need to solve $Ax=b$ in about 1 million dimensions. Furthermore, A is only accessible through matrix vector products, and these are noisy/inexact.
Is there any solver with Python interface I can try ...
- 1,124
7
votes
2
answers
2k
views
When is it easy to invert a sparse matrix?
(Crossposted on cstheory.SE)
When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
- 1,124
2
votes
1
answer
48
views
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I'm looking to solve numerically the following equation for $(d,d)$ variable $X$, in Einstein summation notation
$$M_{ijkl}X_{kl}=N_{ij}$$
Where $M$ is a $(d,d,d,d)$ 4th-moment tensor of random ...
- 1,124
1
vote
0
answers
384
views
Is there any function to calculate condition number of sparse matrix in Eigen libraray?
The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values.
However I need to know condition number of a sparese matrix due to slow computation speed using ...
- 193
3
votes
1
answer
110
views
Efficient solution to a structured symmetric linear system with condition number estimation
I have a real-valued linear system $Hx = b$ where $H$ is symmetric matrix** (not necessarily positive/negative definite) with a very particular structure:
$$
H = \begin{bmatrix} D && B \\ B^T &...
- 752
1
vote
0
answers
85
views
2-norm of solution update suddenly becomes zero after a few iterations
I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
- 23
1
vote
2
answers
396
views
How to use the Thomas-Algorithm to the Heat-diffusion-equation correctly
My post is structured in four parts:
I give you some information about the context my principal questions refer to.
I will tell you what I believe to know about the Thomas Algorithm. If I am wrong ...
- 11