Referring to methods for solving linear systems of equations.

learn more… | top users | synonyms

2
votes
1answer
38 views

Matrix Condition Number and 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 ...
1
vote
1answer
146 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
92 views

Solve steady state reaction-diffusion/Helmholtz equation numerically

I am solving a problem of the form: $\frac{\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
102 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
117 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
58 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 ...
1
vote
1answer
63 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
92 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
92 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
163 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
147 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
141 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 ...
0
votes
0answers
33 views

Does cyclic reduction require a square mesh for 2D FEM/FDM?

In a 2-dimensional finite difference method or finite element method (triangular elements, each node is connected to 6 neighbors), each node has a matrix entry to its horizontal and vertical ...
4
votes
2answers
100 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
101 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 ...
1
vote
3answers
97 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 ...
0
votes
0answers
39 views

LaPlacian 3D example 34.c - how do you invoke multiGrid

I am having trouble running this code while exercising the ksp_type GMRES pc_Type mg -da_refine 1. Error Reports arguments are incompatible I read somewhere the pc_type MG works with all of the ...
3
votes
2answers
184 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
135 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
162 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} ...
1
vote
3answers
143 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 ...
11
votes
2answers
248 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
157 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
vote
0answers
110 views

How to solve sparse linear systems using CPUs and GPUs?

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
220 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
votes
2answers
131 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
155 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
81 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 ...
8
votes
2answers
782 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
287 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix A (10000*10000), if Aij is 1, then ith and jth variables can take 1 simultaneously, if it's 0, then it's ...
0
votes
1answer
58 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 ...
3
votes
3answers
224 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} ...
2
votes
1answer
81 views

Finding Interior eigenvalues using Davidson algorithm

Is it possible to find interior eigenvalues closer to some lambda using Davidson method. I was searching online but found that most people use Jacobi-Davidson method for that. Thanks
5
votes
0answers
95 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 ...
2
votes
0answers
59 views

Adaptive Mesh vs Uniform Mesh for multiple source/boundary/initial Data

I'm going to ask some beginners' questions. Adaptive mesh can save many DOFs than a uniform mesh. But it also needs to solve linear systems changing with mesh adaptive process. Is this not problem? ...
3
votes
2answers
210 views

Solving Newton-Raphson step with ill-conditioned sparse matrix

I am trying to build a complex simulator for the transport of mass & heat in porous media. I am currently following coarsely the algorithm laid out in an older software and have got the simulator ...
4
votes
1answer
101 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
1
vote
1answer
110 views

Problem with convergence of Jacobi iterative algorithm

I'm dealing with Jacobi iterative method for solving sparse system of linear equations. For small matrices it works well and gives right answers even if matrix is not strictly diagonal dominant, ...
0
votes
1answer
83 views

How to use TrangularView class in Eigen C++

For a nonsingular lower or upper triangular square matrix $A$, how to solve such linear system in Eigen: $$A x = b$$
2
votes
1answer
110 views

Question about extending Tikhonov regularization

I know that the Tikhonov regularization of a linear system has an analytical solution given by: \begin{equation} \hat{\mathbf{x}} = \mathrm{arg\;min}\left( \left| \mathbf{Ax} - \mathbf{b} \right|^{2} ...
2
votes
2answers
82 views

Advice on the regularisation of a linear problem

I'm numerically inverting an integral transform using a method suggested by a scicomp user from an earlier question. The problem is as follows: I wish to estimate $f(x)$ for a given $F(y)$, both of ...
2
votes
1answer
148 views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
2
votes
1answer
80 views

Implicit Finite difference scheme for a PDE with only one boundary

I am looking at a few reaction-diffusion equations of the form $\frac{dP}{dt} = D\left(\frac{d^2P}{dr^2} + \frac{2}{r}\frac{dP}{dr}\right) - a(P)$ I know the initial conditions and the boundary ...
2
votes
3answers
169 views

Sparse, underdetermined system of linear equations

I'm looking for an algorithm to solve the underdetermined system of linear equations $$\mathbf{A}\,\mathbf{x} = \mathbf{b}$$ with $\mathbf{A} \in \mathbb{R}^{n\times n}$, $\mathbf{b} \in ...
2
votes
1answer
141 views

How to re-use the coefficient matrix decomposition result when solving linear systems by Eigen C++

My problem needs to solve dense symmetric linear systems something like: A x = b, A y = x, ...
2
votes
1answer
39 views

What is the fomula of polynomial time of solving positive definite symmetric linear system

For a positive definite symmetric linear system, Cholesky decomposition based method should be the best solver which has a rough n^3/3 flops requirement. What is ...
3
votes
1answer
99 views

Constrained System / Combinatorial Problem

Let $x\in \mathbb{R}^{n}$, $Y\in \mathbb{R}^{mxn}$. We can then define: $row_{i}(Y)=$ $i^{th}$ row of $Y$ $column_{i}(Y)=$ $i^{th}$ column of $Y$ $x_{i}=i^{th}$ element of $x$ $sum(x)=$ sum of ...
3
votes
1answer
167 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
3
votes
1answer
337 views

Solving for null space of a matrix with mkl LAPACK

I want to find a solution for $xA=0$, where $A$ is a square matrix. I know that most of the LAPACK routines solve for $Ax=b$. So I take $A^T$ as a, and set $b=0$. I have an additional restriction of ...
6
votes
1answer
412 views

Solving system of linear equations with cyclic tridiagonal matrix

I have this problem in my textbook: Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} ...