Referring to methods for solving linear systems of equations.

learn more… | top users | synonyms

1
vote
0answers
49 views

Solving system of equations with zeros on diagonal [on hold]

I am using finite elements, Newton Raphson technique and MUMPS direct solver, to solve for $P$ in this equation: $$\frac{\delta K}{\delta x} \frac{\delta P}{\delta x}= \frac{\delta K B}{\delta x} + ...
0
votes
0answers
57 views

Implementation of a direct solver in Fortran 90?

My question may be elementary, but it is quite essential as I am getting confused. Here I am supposed to solve the following equation: $Ax=B$ From my understanding I have options of using either ...
1
vote
1answer
88 views

Skyline solver for AX=B where A is symmetric skyline matrix

I am looking for a simple subroutine in Fortran 90 (GNU Compiler) to solve linear equation of the type $AX=B$, where $A$ is an $n\times n$ symmetric matrix stored in the form of symmetric skyline ...
3
votes
1answer
97 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
4
votes
1answer
87 views

Finding the matrix inverse given a solver for the matrix equation $Ax=b$

So I'm given a solver that can solve for $x$ in the matrix equation $\underset{=}{A} \underline{x} = \underline{b}$ where $b$ can be anything we specify. (NB: A is an NxN matrix). I now want to find ...
3
votes
1answer
71 views

Is the “practical” complexity of linsolve direct solver O(n^2) ?

I recently timed the linsolve direct solver and I was kind of shocked to see that the solver seemed to be scaling quadratically even upto a 1000 dimensions. Specifically I ran the following code and ...
1
vote
1answer
107 views

How efficient (compared to “normal” methods) is using a sparse finite difference matrix to solve differential equations?

Any differential operator can be written as a finite difference matrix acting on a vector of values. I recently used it to solve $\Delta A = j$ by writing the Laplacian as a finite difference ...
7
votes
1answer
132 views

Which preconditioning for large linear elasticity problem?

The problem I want to solve is the displacement formulation of the linear elasticity : $$ \nabla \cdot \sigma = 0 \quad \text{in} \quad \Omega \\ \sigma = \lambda ( \nabla \cdot u ) I + \mu (\nabla ...
3
votes
2answers
122 views

Solving a system of linear equations with only an approximate solution

I have a system of linear equations that is derived partially from experimental data. Theoretically, the system should have a single, exact solution; however, experimental error causes it to not have ...
2
votes
1answer
57 views

Solving new linear system that comes from an $p$ enrichment

Let's say I am solving a simple Poisson problem using a Mixed (DG) finite element method. If we use orthogonal polynomials as basis functions we can write the finite-dimensional linear system as $$ ...
2
votes
0answers
50 views

Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?

I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence ...
2
votes
0answers
80 views

FLOPS of a linear system

I have two questions that I want to ask. Consider the following system: $$BM = A$$ i) $B$ is a $n$ by $n$ tridiagonal matrix and $A$ is a diagonal matrix. What is the leading order computation cost ...
5
votes
2answers
109 views

Does this partial eigen-expansion have a name?

This question is a follow-up to this one. Let $A\in \mathbb{R}^{n\times n}$ be large, sparse, symmetric and positive definite. Suppose for I already know $m<n$ eigenpairs of $A$, corresponding to ...
2
votes
0answers
38 views

Suggestions for an out-of-core sparse solver

I have a sparse $2\times10^5$ by $2\times10^5$ matrix with $3.2\times10^9$ non-zero elements. I want a sparse solver with out-of-core functionality. I have attempted to use Intel's ...
2
votes
1answer
76 views

Solve FEM matrix from coupled system

I'm developing an FEM solver for a coupled system. I have diffusion and potential equations which result in positive definite matrices for each equation, but the coupling makes the overall system ...
6
votes
0answers
66 views

What are some ideas to preprocess / precondition the following linear system?

Let $A\in \mathbb{R}^{n\times n}$ symmetric and positive semidefinite, and $\omega\in \mathbb{R}\setminus\{0\}$. I am interested in solving the following linear system for a range of values of ...
6
votes
0answers
89 views

What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
4
votes
1answer
110 views

What factors are relevant when deciding between GMRES and schur complement solves?

Suppose I have a linear system $$ \left\lbrack \begin{array}{cc} M_1& S\\ S^{\mathrm{T}}& M_2 \end{array} \right\rbrack \left\lbrack \begin{array}{c} X\\ Y\end{array} \right\rbrack= ...
5
votes
1answer
188 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 ...
5
votes
1answer
73 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} ...
4
votes
1answer
93 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
139 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
98 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 ...
4
votes
1answer
88 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
0answers
54 views

solve linear system of equation of a large sparse symetric positive definite matrix

I want to invert large matrices ($10^4x10^4$ to $10^6x10^6$) but sparce (less than 100 non-zero entries per line) on clusters with 16 to 48 processors per node. I'm looking for an efficient method to ...
0
votes
1answer
49 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}$ ...
1
vote
0answers
88 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 ...
6
votes
2answers
341 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 ...
2
votes
1answer
81 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
120 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 ...
8
votes
1answer
227 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
0answers
235 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 a popular for the scientific computation ...
1
vote
1answer
61 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
224 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. ...
5
votes
1answer
346 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
135 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
185 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
165 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
301 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 ...
2
votes
1answer
216 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
167 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
116 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
197 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
130 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 ...
2
votes
1answer
120 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 ...
0
votes
1answer
247 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
102 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 ...
9
votes
4answers
221 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 ...
5
votes
1answer
168 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 ...
3
votes
3answers
217 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 ...