Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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&...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}$. $\...
user avatar
  • 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. \...
user avatar
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 ...
user avatar
  • 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(...
user avatar
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 \...
user avatar
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$)...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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://...
user avatar
  • 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,...
user avatar
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'...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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_{...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 &...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
8