Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
4
votes
1answer
179 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 ...
4
votes
1answer
249 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 ...
4
votes
2answers
126 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'...
4
votes
1answer
191 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 ...
1
vote
1answer
156 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 ...
0
votes
1answer
94 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}$ ...
2
votes
0answers
655 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 $...
7
votes
2answers
2k 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.)...
2
votes
1answer
102 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 ...
1
vote
0answers
491 views

General algorithm to solve systems of symbolic equations

I want to simplify (solve) a system of linear + nonlinear symbolic equations as much as possible. the equations are of random orders, without differentiation. is there a general & well-known ...
13
votes
1answer
868 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$ ...
0
votes
1answer
1k 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....
2
votes
1answer
249 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 ...
1
vote
2answers
1k 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'...
5
votes
0answers
714 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 ...
0
votes
1answer
546 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: ...
3
votes
2answers
217 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 ...
2
votes
1answer
696 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 ...
8
votes
2answers
1k 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 ...
0
votes
1answer
506 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 ...
2
votes
1answer
343 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 ...
1
vote
1answer
311 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 ...
4
votes
0answers
142 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 ...
1
vote
3answers
581 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) - \...
1
vote
2answers
1k 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 ...
3
votes
1answer
249 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"...
0
votes
1answer
963 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, ...
5
votes
1answer
142 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{...
9
votes
4answers
342 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}$...
7
votes
1answer
353 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\...
3
votes
3answers
682 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'...
5
votes
2answers
217 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,$$ ...
0
votes
1answer
425 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 ...
2
votes
3answers
746 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 ...
6
votes
2answers
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, ...
2
votes
1answer
2k 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 + ...
3
votes
2answers
193 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}...
1
vote
3answers
667 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 ...
13
votes
2answers
703 views

preconditioning a krylov method with another krylov method

In method 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
3answers
174 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 ...
3
votes
1answer
3k 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 ...
11
votes
2answers
367 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 ...
3
votes
2answers
204 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 ...
4
votes
1answer
311 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
vote
1answer
306 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 (...
13
votes
3answers
3k 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 ...
3
votes
2answers
371 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix $A$ ($10000\times10000$), if $A_{ij}=1$, then $i$th and $j$th variables can take 1 simultaneously, if it ...
0
votes
1answer
85 views

Least squares fitting

I have the following equation I came across which was solved using least squares $x = \sum_{n=1}^{N} A_{n} y_{n}$ Where $x$ is a $m \times p$ matrix and $y$ would be of size $m \times p$ as well ,...
5
votes
4answers
1k views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...
8
votes
0answers
222 views

Wanted: sequences of linear systems for recycling Krylov solver analysis

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...