# Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

351 questions
Filter by
Sorted by
Tagged with
147 views

### Regarding impractical usage of direct solvers of linear systems [closed]

Since the computational complexity of direct elimilation methods for solving linear systems is $O(n^3)$, it's not practical when the number of dofs is large. But how large would you call it a large ...
304 views

### Is lapack getri numerically the same as getrs with identity matrix as RHS?

I was just wondering, in case of computing B=inv(A), suppose I is the identity matrix (diagonal), After obtaining the ...
191 views

### How is the dense system usually dealt with in spectral method?

Unlike finite element (FEM) or finite difference methods (FDM), where the original PDE is transformed into a sparse linear system, spectral methods return a dense linear system. For a large system, it'...
164 views

85 views

### What does it take to prove that a multigrid algorithm scales linearly with system size?

It is my understanding that the multigrid solution techniques are generally the preferable method to solve large Poisson problems. Now assume I have written a multigrid solver that is tailored to my ...
813 views

### Thomas algorithm for 3D finite difference

For 1D finite difference, the resulting linear system is tri-diagonal and can be solved in O(n) using the Thomas algorithm. I am trying to solve a finite ...
180 views

### Difference between explicit and implicit preconditioning

What is the difference between an explicit and implicit preconditioner?
56 views

$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\... 2answers 291 views ### Solving a singular system of linear equations with smallest solution? I have a problem where I am solving a system of linear equations but sometimes the system results in a singular matrix which cannot be easily solved. In this case I would like that those rows for ... 0answers 56 views ### Preconditioning matrix with known spectrum Assume I know all eigenvalues of a matrix A fall into a certain set \Omega \subset \mathbb{C}. Is there any way I can exploit this knowledge to design a preconditioner for A? Some further ... 0answers 145 views ### Updating factorization of Laplacian (add/remove edges) For a graph G=(V,E), recall that the unweighted Laplacian is L:=D^\top D, where D\in\{-1,0,1\}^{|E|\times|V|} is the graph "gradient" operator that subtracts adjacent vertex values onto edges. ... 2answers 259 views ### CHOLMOD implementation I am working on a domain decomposition code in C that uses CHOLMOD to approximate grid values for a PDE in each sub-domain. The issue I have is that the methods use Matrix Market format, which is not ... 1answer 202 views ### Open Source Linear Algebra Library I am making a code in C that requires the equivalent of Matlab's '\' command for a linear system of the form AX=B where A is an NxN matrix and X, B are Nx1 vectors- i.e a code that performs X=A\B that ... 0answers 34 views ### Difference between Chebyshev first and second degree iterative methods Consider linear equation Au = f. We want to solve it with iterative method (assuming A is good). First order iterative method is:$$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$The second degree ... 1answer 116 views ### Does algebraic multigrid reuse its coarse grids? Admittedly, I'm new to the subject, so this is probably a really simple question. Let's assume I want to solve the (large sparse) linear system Ax = b multiple times with algebraic multigrid and b ... 1answer 234 views ### Parallel linear algebra without OpenMP I have searched through the archives without success. Apparently, the question is simple: What linear algebra library can I use that is parallel (shared memory) but without OpenMP? As far as I've ... 1answer 111 views ### NONLINEAR ENERGY MINIMIZATION EXAMPLE I am learning about FEM methods and nonlinear optimization. I would like to try my nonlinear trust region solver on some simple nonlinear problem. What would be good example to implement for ... 0answers 202 views ### Once and for all: Which FEM plattform should I use for a very large multiphysics simulation? I'm fooling around with the decision on how to build a multiphysics simulation for too long now (also several questions in this forum). First, I thought it would be possible/necessary to write most of ... 1answer 103 views ### Numerical method for solving a system with positive definite blocks I have a system with below coefficient matrix$$ C = \begin{pmatrix} A & B^T \\ B & D \end{pmatrix},$$where, A and D are square and positive definite. Furthermore, if B be square, ... 2answers 910 views ### Solving linear system Ax=b with Hessenberg matrix using lapack I need to solve a linear system of the form$$Ax = b$$where A is upper Hessenberg matrix with the lower bandwidth equal to 1, b is the RHS vector and x is the solution vector. I have a C++ ... 1answer 245 views ### Robust smoothers for geometric multigrid I'm searching for robust smoothers for geometric multigrids. By robust I mean: Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin), Parallel (suitable for ... 1answer 405 views ### "Cookbook" about iterative linear solvers and preconditioners I'm using a lot of linear solvers and preconditioners, but mostly, they are magical black boxes to me. Since I'll also have to implement some of them in future, I would like to learn a bit more, ... 1answer 195 views ### Single Precision a x plus y (SAXPY) terminology I've been reading books which refers to vector update operations of the form: y := y + ax, where y and x are vector variables and a is a scalar as SAXPY. I understand ax plus y part, but why "single ... 1answer 680 views ### Solving a set of linear equations with block structure and weak coupling I have a standard set of linear equations Ax=b where the Hessian matrix A has the special block structure as shown: A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}, x= \begin{... 1answer 228 views ### solving tridiagonal system with multiple right hand sides I need to solve a tridiagonal system (positive definite, diagonally dominant) Ax = b in a time stepping loop. A \in \mathbb{R}^{N \times N} remains constant but b changes during each time ... 1answer 380 views ### Linear Systems with Multiple Right Hand sides I am interested in solving a sequence of linear systems of the form:$$A x_i = b_i$$That is, all the systems use the same matrix A but they have different right hand sides. The matrix A is sparse ... 1answer 507 views ### Methods for solving rectangular, full-rank systems of equations -- which is best? Suppose I have a large, sparse, m \times n matrix A, with m \gt n and \text{rank}(A) = n. I wish to solve Ax=b. Suppose I know that A has the following characteristics: A is somewhat ... 3answers 867 views ### role of initial guess for iterative linear solver Suppose we use a preconditioned iterative solver for a linear system. If the initial state for the solver can be chosen very close to the exact solution - does this reduce requirements for the ... 1answer 2k views ### Solving linear systems with ill-conditioned matrices As per suggestions of the people from MathOverflow, I'm reposting my question here: I'm currently trying to solve a linear system Ax = B, where the matrix A is ill conditioned (i.e. nearly ... 0answers 81 views ### Solve for D in R^{T}DSDR = Id Given that R is a rectangular matrix, D is a diagonal, square matrix and S being a square matrix along with the fact that both D and S are invertible. S in this specific case can be ... 1answer 263 views ### Resources for solving mixed left and right matrix equations I'm looking to solve a matrix equation and not sure where to start looking for resources. The equation is$$AX + XB = C\,,$$where A\in\mathbb{R}^{n\times n}, B\in\mathbb{R}^{m\times m}, C\in\... 1answer 234 views ### Mathematical Complexity of Sparse Solvers For a system \mathbf{x=Da}, there exist a lot of algorithms to estimate sparse vector \mathbf{a}. I wish to know the big-O mathematical complexity of 1) orthogonal matching pursuit (OMP) both ... 0answers 212 views ### Solving system of equations with zeros on diagonal [closed] 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} + A$... 0answers 649 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 ... 1answer 1k 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 ... 1answer 263 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 ... 1answer 111 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 ... 1answer 553 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 ... 1answer 416 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 ... 1answer 597 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 \... 2answers 4k 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 ... 1answer 75 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$$ ... 0answers 256 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 behavior.... 2answers 130 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 ... 1answer 140 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 ... 1answer 150 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 ... 1answer 151 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$\...
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 ...
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= \...