Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
350
questions
5
votes
1answer
80 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.
\...
3
votes
0answers
47 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 ...
1
vote
0answers
48 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(...
0
votes
1answer
41 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
vote
1answer
84 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$)...
0
votes
0answers
47 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 ...
4
votes
2answers
207 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, ...
3
votes
0answers
69 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 ...
7
votes
2answers
164 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 ...
0
votes
2answers
87 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 ...
2
votes
3answers
158 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 ...
-1
votes
1answer
46 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 ...
2
votes
1answer
126 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 ...
0
votes
1answer
68 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 ...
1
vote
1answer
56 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.
5
votes
1answer
133 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://...
-1
votes
1answer
32 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
0answers
37 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'...
3
votes
0answers
64 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
vote
1answer
116 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 ...
5
votes
1answer
197 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 ...
1
vote
0answers
69 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 ...
3
votes
0answers
45 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 $A_{jk} = A_{kj}$ but $A_{jk} \neq ...
0
votes
0answers
37 views
How can the choice of coarsening factor affect Multigrid's convergence?
The linear system $Ax=b$ is coming from the discretization of an elliptic PDE. Multigrid method is used in order to solve it. Suppose $c_0$ is the coarsening factor on level 0 and $c_m$ the coarsening ...
1
vote
0answers
67 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. ...
0
votes
0answers
44 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 ...
6
votes
2answers
472 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 ...
2
votes
1answer
43 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
vote
0answers
216 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 ...
3
votes
1answer
102 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 &...
1
vote
0answers
81 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 ...
1
vote
2answers
259 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 ...
0
votes
0answers
62 views
The error in SOR algorithm suddenly falls to zero when it reaches 1e-7 range
I am solving the Poisson equation for heterojunction using Fortran90. I use the SOR algorithm to arrive at the potential profile.
I see the weird behavior where the error (the difference between the $...
0
votes
0answers
32 views
Abnormalities when using SOR to solve the Poisson Equation
I am trying to solve the Poisson equation for Heterostructures using SOR. The equation to solve looks lik
I have discretized the Poisson equation using finite difference and my code is written in ...
0
votes
1answer
107 views
Is it possible to predict solution oscillation before solving the system by looking at coefficient matrix?
Question
When it is about solving a system of equations, is it possible to predict that whether high-frequency noise (e.g. checker-boarding) is likely to appear in the converged solution by looking at ...
4
votes
2answers
155 views
Solve two-player game - minimize the l-infinity norm of a matrix-vector product
I have a matrix $M$ with non-negative real entries, and I would like to minimize the objective function
$$\Phi(v) = \|Mv\|_\infty,$$
where $v$ is constrained to be a probability vector, i.e., $v_1+\...
0
votes
0answers
62 views
Preconditioning the $[1 \quad-2 \quad 1]$ Finite Difference matrix
Let $A$ be the well known tridiagonal matrix coming from the 1D Finite difference discretization of the Laplacian, with stencil $\frac{[1 \quad-2 \quad 1]}{h^2}$.
The system $Ax = b$ is very large, so ...
0
votes
1answer
148 views
Solving large sparse system
I am working on a problem with very large sparse matrices. I'd like to compute $A^{-1} B$, that is a crucial part of converting DAE to ODE (and there is no workaround). Here size of $A$ is 2E+5 x 2E+5 ...
1
vote
1answer
154 views
Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero
I have a set of linear equations, $Ax=b$. And about half of the elements in the right-hand side (vector $b$) are equal to zero. My system matrix $A$ is a sparse complex matrix. And $A$ is in the size ...
7
votes
2answers
317 views
Is there an iterative solver for dense matrices with possible zero diagonal entries?
Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
0
votes
0answers
62 views
Solver for large dense BVP system in python
I have a large system of boundary value problems of the form
$$ \frac{d^2 y }{dt^2} = C(t) y + b(t), $$
where the variable $y$ is a vector that has anywhere from 50 to around 500 components, $C$ is a ...
0
votes
1answer
131 views
Solving a sparse linear system using transpose of lower triangular matrix without copying
I have a sparse lower-triangular matrix $L$, and a right-hand side $b$, and I'd like to solve the linear system
$$L^T x = b$$
but without explicitly creating $L^T$. Ideally, I could write something ...
2
votes
1answer
99 views
Solving an m x m symmetric linear system involving a matrix multiplication versus an (n+m) x (n+m) system
Suppose that $R$ and $D$ are an $n \times m$ and $m \times m$ matrices. Assume that $m \ll n$ and that $D$ is positive definite. We would like to solve the system $(R^T R + D) x = R^T b$. This ...
3
votes
1answer
224 views
Is there any reason to scale a matrix before (sparse) Cholesky decomposition?
I have a sparse symmetric positive-definite matrix $M$ and I expect the entries in some rows/columns to have very different orders of magnitude (up to a factor of $10^8$) than the entries in others.
...
1
vote
2answers
243 views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
3
votes
1answer
274 views
What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix?
I have a symmetric positive semi-definite matrix, i.e., a laplacian and wonder what may happen when I use a CG solver, that is an algorithm for positive definite matrices.
What happens when the ...
2
votes
2answers
103 views
Solution of symmeric/non-symmetric linear system
I would like to understand what happens in the following:
I have a really simple Poisson problem, in 1D, with $u_0 = u_N = 0$. I assembled the stiffness matrix and the right-hand side, and I applied ...
4
votes
2answers
181 views
More stable method of back substitution?
I've been tinkering a little in Fortran (2008) and wrote the following to solve
$Rx=b$ for $R\in\mathbb{R}^{n\times n}$ upper-triangular, $x,b\in\mathbb{R}^n$.
My code looks like this:
...
1
vote
1answer
111 views
Solving triangular matrix equations on a GPU
Suppose I have these two $N\times N$ lower triangular banded matrices:
$A = \begin{bmatrix}
a_0 & & \\
a_1 & a_0 & \\
a_2 & a_1 & a_0 \\
a_3 & a_2 & a_1 & a_0 \\
&...
1
vote
1answer
75 views
Parallel solution of PDEs
Which is the best approach to solve a PDE in parallel:
1.To split the mesh the mesh in N parts and every processor works on its own part or
2.To take the global linear system Ax=b and solve it in ...
