Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
403
questions
5
votes
1
answer
240
views
What is a good way to solve the following linear system? (repeatedly)
Let $n,m\in \mathbb{N}$ be such that $m\ge n$.
Let $M_1\in \mathbb{R}^{n\times n}$, $\{M_{2},M_{3} \} \subset \mathbb{R}^{m\times m}$ be symmetric positive definite and computationally cheap to ...
- 1,000
5
votes
1
answer
163
views
Large scale triangular least squares
I have to solve the following least squares problem:
\begin{equation}
\| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2
\end{equation}
...
- 121
4
votes
1
answer
241
views
Best solver/preconditioner for least-squares finite element method
I have seen a lot of literature, lecture videos, etc. on solvers/preconditioners for non-symmetric and/or indefinite systems. However, now I want to solve the mixed poisson/Darcy equation using the ...
- 791
4
votes
1
answer
338
views
Appropriate iterative linear solver for an eigenvalue problem
I'm trying to solve a generalized eigenvalue problem
$$Ax = \lambda Bx, \quad A = A^\top > 0,\; B = B^\top > 0$$
with $\lambda \approx \sigma$ using Rayleigh Quotient Iteration (RQI) (RQI is ...
- 165
4
votes
2
answers
143
views
Under what circumstances can two (nearly) identical sparse matrices give different solutions to Mx = b?
Suppose I have two sparse matrices, $A$ and $B$, of size $N \times N$. They each have the same sparcity pattern ("footprint"). They each also have values which in theory should be identical, but aren'...
- 263
4
votes
1
answer
321
views
Choosing preconditioner for unsymmetric pressure-velocity coupled system
I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
- 41
1
vote
1
answer
230
views
solve linear system of equation of a large sparse symetric positive definite matrix
I want to invert large matrices ($10^4 \times 10^4$ to $10^6 \times 10^6$) but sparse (less than $100$ non-zero entries per line) on clusters with $16$ to $48$ processors per node.
I'm looking for an ...
- 262
1
vote
1
answer
160
views
Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition
I have the following quadratic form I need to evaluate:
$x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors.
Now assume that I am given for free both $A^{-1}$ ...
- 285
2
votes
0
answers
831
views
Solving a system of 4 coupled PDEs representing variable diffusivity
I have four partial differential equations representing mass conservation of two compressible fluid phases (marked by subscripts $p1$ and $p2$) in two different continuum media (marked by subscripts $...
user5510
8
votes
2
answers
3k
views
Solving Linear Systems in Julia
To give you some context,
I am currently implementing a simple finite element solver in Julia. I am getting run-times that are 70% of a Matlab code. (Both codes are essential equivalent in structure.)...
- 181
2
votes
1
answer
121
views
How do I make sparse solvers to accept custom matvec function insted of matrix?
I have tried it with Lis, Intel mkl and PETSc. Everywhere you need to pass an actual matrix ...
- 193
14
votes
1
answer
1k
views
How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?
Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence:
Compute the residual $r_i = b-Ax_i$
...
- 849
0
votes
1
answer
3k
views
MATLAB: code for restarted gmres
I have a question about Matlab and restarted gmres. I would like to use gmres.m provided here. This code seems to be popular for the scientific computation newcomer....
- 129
2
votes
1
answer
548
views
Incomplete Cholesky
Is there an efficient way to perform an incomplete Cholesky factorization on a symmetric positive definite sparse matrix (CSR format), in order to use it as a preconditioner for a CG solver? Is there ...
- 139
2
votes
2
answers
2k
views
Solve large dense positive-definite linear system
Which method should I choose to solve a large (~20 000 variables) dense symmetric positive-definite, possibly ill-conditioned, system of linear equations?
The system will be solved for two vectors. I'...
- 21
2
votes
1
answer
243
views
Solving sparse linear equations with an iterative, out-of-core algorithm
Is there an iterative sparse parallel linear equation solver with out-of-core capabilities?
I need to solve a very large system of equations. I have implemented direct sparse parallel solvers in-core ...
- 139
15
votes
1
answer
1k
views
Are direct solvers affected by the condition number of a matrix?
If I were to solve a relatively small problem, that is, a problem that can be handled by a direct method like LU, then does the condition number of the linear operator affect the accuracy of the ...
- 791
5
votes
0
answers
878
views
Can Gauss-Seidel/SOR (preconditioned?) be applied to a non-diagonally dominant matrix?
After applying finite difference method to a Laplace/Poisson problem always arises a diagonal dominant system of equations that can be solved with Gauss-Seidel or SOR methods. If the original PDE does ...
- 223
0
votes
1
answer
952
views
MATLAB: Backslash operator using symbolic variables with an overdetermined system
I have an overdetermined system (too many equations), expressed as Ax=b, in MATLAB. When I try to solve it using A\b, I receive the error:
...
- 103
3
votes
2
answers
228
views
Which software packages can solve linear systems that are not stored
I have matrices that are extremely easy to compute pointwise, but are too large to store. (they are not sparse)
On the MATLAB site I was told MATLAB doesnt support computations with non-stored ...
- 799
2
votes
1
answer
973
views
Efficient compressed row storage Gauss Seidel C/C++
I am trying to figure out why my sparse (CRS) Gauss Seidel solver is so slow. I tried to find an implementation of the Gauss Seidel method in sparse format online but could only find implementations ...
- 21
9
votes
2
answers
2k
views
Does the matrix condition number affect accuracy of iterative linear solvers?
I have a rather specific question regarding the condition number. I run FEM simulations which have multiple length scales to them which results in a huge disparity between the largest entries and the ...
- 113
0
votes
1
answer
1k
views
Avoid arithmetic overflow in matrix multiplication
I am solving the following matrix equation for $\mathbf{x}$:
$$(J^{\mathbf{T}}J)\mathbf{x}=J^{\mathbf{T}}\mathbf{r}$$
$J$ is $m\times n$ matrix
$\mathbf{x}$ is vector of size $n$
$\mathbf{r}$ is ...
- 393
2
votes
1
answer
486
views
Construct a preconditioner for the linear system $Ax = b$ from a different matrix
When I use PETSc to solve my linear systems, I always use the subroutine
PetscErrorCode KSPSetOperators(KSP ksp,Mat Amat,Mat Pmat)
where ...
- 183
1
vote
1
answer
528
views
Direct or iterative solver for ill-conditioned problems
I have to solve an ill-conditioned sparse matrix. Once I read that iterative solvers are the better tool for such problems. Is that true? If yes, why?
- 11
1
vote
1
answer
363
views
Solve steady state reaction-diffusion/Helmholtz equation numerically
I am solving a problem of the form:
$\dfrac{\partial u(x,y,t)}{\partial t} = \nabla^2 u(x,y,t) - f(x,y,t)u(x,y,t) - \kappa(x,y,t)$
At the moment, I am solving this at each time step by assuming a ...
- 121
4
votes
0
answers
161
views
How big a matrix can we row reduce in reasonable time?
I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank).
The good news is that I work mod 2 and the ...
- 141
1
vote
3
answers
916
views
Solve diffusion equation with linear source term
I would like to solve numerically the diffusion equation, where the sink term depends linearly on the field, and there is field-independent sink:
$\frac{\partial^2 u(x)}{\partial x^2} =f(x)u(x) - \...
- 121
2
votes
2
answers
3k
views
Time complexity for sparse direct solver for SPD system with respect to number of equations, bandwidth, number of nonzeros?
I am looking for information on the time complexity for solving sparse system Ax=b with direct solver. This system results from a finite-element discretization of an elliptic problem. The matrix A ...
- 161
3
votes
1
answer
315
views
non-smooth convex c++ solver
I happened to know that there are advanced established techniques for non-smooth convex optimization in research. For example, these two papers:
Nesterov, "Smooth minimization of non-smooth functions"...
- 243
0
votes
1
answer
1k
views
Is it possible to output the matrix condition number from pardiso (MKL)? [closed]
I am assuming the pardiso solver calculates (or estimates) the condition number before proceeding to the solution phase.
Is there a way to make pardiso output the condition number?
Alternatively, ...
- 317
6
votes
1
answer
206
views
Solving Generalization of Saddle point problem
I am interested in knowing if there is a generalization of the Uzawa iteration for the linear problems of the form
$$\left[ \begin{array}{ccc}A& B^T&0\\
B&0&C^T\\
0&C&0 \end{...
- 61
9
votes
4
answers
411
views
Fast explicit solution for $\mathbf{A}\mathbf{x} = \mathbf{b}$, $ \mathbf{b} \in \mathbf{R}^3$, low condition number
I am looking for a fast (dare I say optimal?) explicit solution the 3x3 linear real problem, $\mathbf{A}\mathbf{x} = \mathbf{b}$, $\mathbf{A} \in \mathbf{R}^{3 \times 3}, \mathbf{b} \in \mathbf{R}^{3}$...
- 802
9
votes
1
answer
532
views
Least-squares for a diagonal matrix
This is a follow-up to a different question I asked with more detail.
For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\...
- 1,341
3
votes
3
answers
1k
views
Large overdetermined system of linear equations
I'm looking for a method to solve a large overdetermined system of linear equations in a least squares sense. The matrix is dense.
I'd like to use a method that works even with limited memory (we can'...
- 213
5
votes
2
answers
277
views
Solving "Hadamard systems"
Suppose we have two matrices $A$ and $B$ (we can assume they're symmetric; if absolutely necessary I think they may be positive definite). Then, is there any technique for solving $$(A\circ B)x=b,$$ ...
- 1,341
0
votes
1
answer
658
views
Fastest linear solver for sparse positive semidefinite, striclty diagonally dominant matrix
What is the state of the art for fastest linear solver for sparse, positive semi definite and strictly diagonally dominant matrix with N varies from ~700 to ~3000, and about a 1/16 of the matrix is ...
- 83
2
votes
3
answers
1k
views
Test set for linear solvers
Lets assume I have a iterative linear system solver, e. g. this one.
Whats the typical approach on verifying and testing this kind of solvers? Is there a standard test set of linear systems one ...
- 23
9
votes
2
answers
2k
views
Solving Lx = b for big sparse Laplacian matrices
What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
- 193
2
votes
1
answer
3k
views
How do I simultaneously minimize two different functions who have the same inputs?
I want to minimize two different functions simultaneously who have the same inputs. The functions are both linear and non-exponential.
$$F_1(X_1, X_2) = a_1X_1 + a_2X_2$$
$$F_2(X_1, X_2) = b_1X_1 + ...
- 21
3
votes
2
answers
215
views
Solving linear system with 6 equations and 22 unknowns for six of the unknowns
I am trying to find the solution for the M variables in the following system.
\begin{equation}
0 = C_{b} M^{b}_{x} - M^{a}_{x} k_{2a} + M^{a}_{y} \left(\omega - \omega_{a}\right)\\
0 = C_{a} M^{a}_{x}...
- 133
1
vote
3
answers
869
views
External solver in Abaqus/Ansys
Is it possible to call an external linear solver from Abaqus and/or Ansys?
This solver (which is supplied by me) would get the sparse matrix A and the right hand side vector b as inputs, and would ...
16
votes
2
answers
1k
views
Preconditioning a Krylov method with another Krylov method
In methods like gmres or bicgstab it could be attractive to use another Krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
1
vote
3
answers
187
views
Surface normals integration
I am trying to reconstruct a 3D surface given the normals of the unknown surface. Reading through this paper on section 4 they say
[...] denote the surface by $z(x,y)$. The directions of the ...
- 1,029
4
votes
1
answer
6k
views
GPU-accelerated libraries for solving sparse linear systems
There are several libraries to (iteratively) solve large sparse linear equation systems in parallel on a number of CPUs. Our parallel cluster also has attached powerful GPUs, but so far, I did not ...
- 1,463
11
votes
2
answers
445
views
Do black-box preconditioners for matrix-free methods exist?
Jacobian-Free Newton-Krylov (JFNK) methods, and Krylov methods in general, can be very useful because they don't require explicit storage or construction of a matrix, only the results of matrix-vector ...
- 2,365
3
votes
2
answers
263
views
Does length unit in FEM affect numerical condition?
I try to solve a system of coupled PDEs using FEM. Unfortunately, the originating matrix has very poor condition. After days of double checking and thinking, I suspect the following reason:
Given a ...
- 1,463
4
votes
1
answer
448
views
Linear equation system: Direct solver works, iterative solver does not
I have to solve for x in b = A*x, where a is sparse. This works fine with Matlab's mldivide: x = A \ b. Since I will have to use an iterative algorithm for very large A, I'm currently testing Matlab's ...
- 1,463
1
vote
1
answer
447
views
Solver library for matrix-free linear equation system
I will have to solve a large linear system. I'm now looking for a solver that works "matrix-free" (So that I just have to specify a matrix-vector product, but not the matrix). As far as I understand (...
- 1,463
13
votes
3
answers
5k
views
Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system
I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
- 1,899