Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

2
votes
0answers
48 views

Scaling for a nonsymmetric eigenvalue problem

I have an eigenvalue problem emerging from the internal vibro-acoustic coupling. The eigenvalue problem is nonsymmetric but it was proven in literature that it results in real eigenvalues and ...
4
votes
1answer
262 views

Why is the speed of the parts of the LU-decomposition so different?

I know that an easy way to solve the matrix problem $$A\cdot x=b$$ is the LU decomposition $$\begin{split} L,\,U&=\text{lu}(A)\\ y&=\text{solve}(L,\,b)\\ x&=\text{solve}(U,\,y) \end{split}$...
5
votes
2answers
299 views

Solving Poisson equation with current BC using FEM

I have a 3-dimensional domain D, with 3 types of BC which I am trying to solve the Poisson equation on. $$-\nabla \cdot (\sigma(x,y,z)\nabla u)=0$$ Insulator (Neumann BC) Electrode set at some ...
1
vote
5answers
4k views

Fast c++ library to solve very big sparse systems

I am working on a project with electrical circuits, where I am trying to compute the voltages at all the nodes of an electrical circuit. I know that the electrical circuit is a perfect grid, so each ...
1
vote
1answer
158 views

Fast counting of all submatrices of a binary matrix with a full column rank

I have a binary full-rank matrix of size, say, $25 \times 50$. I need to count how many subsets of its columns form matrices with a full column rank, i.e. all the columns in the subset are linearly ...
2
votes
1answer
451 views

Which is the best subroutine available for solving sparse linear system of equations [closed]

I am trying to solve the system of linear equations: $AX=B$. For this currently I am using Intel MKL Pardiso solver. It works well when the order of $A$ is around $13500\times13500$ and below. Above ...
1
vote
0answers
444 views

Tridiagonal Solver in Python

I have a code I'm working on that involves solving a 1D Schrodinger equation using a Crank-Nicolson time step. The code is written in NumPy/SciPy, and I was doing a bit of profiling and discovered ...
1
vote
0answers
158 views

How to reshape matrix into row-major order for MKL DSS?

I would like to use MKL to solve a sparse linear system. I chose the DSS (Direct Sparse Solver) interface, which implements the following steps: ...
2
votes
3answers
615 views

How to get multiple solutions for a optimization problem using any kind of software

I have a optimization problem in which the optimal objective value occurs at multiple point in the feasible space. If I run my problem in LINGO software then it gives me the optimal objective value at ...
0
votes
1answer
93 views

Writing a non-square linear system in standard form $A\cdot{x}=b$

I have spend the last few days working my way through an interesting paper and I'm building a numerical model so I can apply the method. However, I am getting stuck at an "it can be shown" step. I am ...
3
votes
1answer
2k views

Iteratively solving 3D Poisson equation in MATLAB

I have written a function that sets up a sparse matrix A and RHS b for the 3D Poisson equation in a relatively efficient way. The set-up is nothing fancy: I have extended the 2D 5-point stencil to an ...
0
votes
1answer
85 views

Iterative single variable solutions in large linear systems

I have a system where $A$ is a large $n\times n$ marix with fast MVMs. It may have many nonzero entries (albeit in a structured way so as to allow fast MVMs), and is not necessarily diagonally ...
4
votes
1answer
194 views

Test matrices for large sparse overdetermined system of linear equations

I'm working on some c++ code to solve (conjugate gradient, least squares conjugate gradient, LSQR,..) large sparse overdetermined systems of linear equations. There is a twist to my matrices and the ...
3
votes
0answers
94 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
3
votes
0answers
136 views

Fast solution of a heptadiagonal linear system

I have a linear system of the form $\mathbf{A}\mathbf{x} = \mathbf{f}$. If the length of the vector $\mathbf{x}$ is $N$, meaning that there are $N$ unknowns, then the matrix $\mathbf{A}$ has seven ...
1
vote
0answers
83 views

QR via Householder: less computationally complex variants?

I'm a probabilist and need to do a few computations for a rather big linear least squares problem, so I'm trying to optimize the computation as far as is feasible to me. In computing the QR ...
2
votes
1answer
116 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 ...
1
vote
1answer
158 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 ...
1
vote
2answers
111 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'...
0
votes
1answer
127 views

Optimization with Yalmip [closed]

I would like to solve in Matlab the following optimization problem $$\begin{array}{ll} \text{maximize} & \bigg\| \displaystyle\sum_{l=1}^{2}\alpha_l \int_{\tau_{m+l-1}}^{\alpha_1\tau_m+\alpha_2\...
5
votes
2answers
167 views

Solving systems of linear equations with cyclic bidiagonal matrix

I am looking for a good numerical method to solve a linear system (of small/moderate size) with a matrix of the form $$ \begin{bmatrix} a_1 & b_1\\ & a_2 & \ddots \\ & & \ddots &...
1
vote
0answers
83 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 ...
4
votes
1answer
454 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 ...
1
vote
1answer
126 views

Difference between explicit and implicit preconditioning

What is the difference between an explicit and implicit preconditioner?
1
vote
0answers
53 views

bound error for iterative method for solving linear system

$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_\...
0
votes
2answers
162 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 ...
2
votes
0answers
40 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 ...
1
vote
0answers
109 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. ...
0
votes
2answers
109 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 ...
0
votes
1answer
166 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 ...
1
vote
0answers
26 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 ...
5
votes
1answer
102 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 ...
0
votes
1answer
152 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 ...
0
votes
1answer
100 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 ...
4
votes
0answers
187 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 ...
1
vote
1answer
96 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, ...
2
votes
1answer
432 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++ ...
6
votes
1answer
232 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 ...
7
votes
1answer
370 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, ...
0
votes
1answer
110 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 ...
5
votes
1answer
239 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{...
0
votes
1answer
156 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 ...
1
vote
1answer
247 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 ...
3
votes
1answer
238 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 ...
6
votes
3answers
274 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 ...
3
votes
1answer
1k 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 ...
3
votes
3answers
258 views

How to assemble Global matrix (for coupled) problem?

I'm trying to assemble global matrices for the following system. $$ \begin{bmatrix} K& Q\\ Q^T&S \end{bmatrix} \begin{bmatrix} u_h\\ p_h \end{bmatrix} = \begin{bmatrix} f_u\\ f_p \end{...
2
votes
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 ...
4
votes
1answer
157 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\...
0
votes
1answer
168 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 ...