Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

57 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
184 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
8
votes
0answers
244 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 ...
7
votes
0answers
81 views

How to construct an effective preconditioner for this particular problem

A quick introduction to my problem I am currently developing a method for simulation of water waves in three dimensions based on potential flow theory. The computational bottleneck of the method is ...
6
votes
0answers
125 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 ...
5
votes
0answers
181 views

Symmetric sparse direct solvers in scipy

scipy.linalg.solve, in its newer versions, has a parameter assume_a that can be used to specify that the matrix $A$ is symmetric ...
5
votes
0answers
238 views

conjugate gradient for Newton's method with non positive definite Hessian matrix

I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$: $$ \...
5
votes
0answers
741 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 ...
5
votes
1answer
237 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 ...
4
votes
0answers
44 views

Nonlinear least squares optimized Jacobian calculation

I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes: $$ \min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2 $$...
4
votes
0answers
201 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 ...
4
votes
0answers
143 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 ...
3
votes
1answer
84 views

Solve two-player game - minimize the l-infinity norm of a matrix-vector product

I have a matrix $M$ with non-negative real entries, and I would like to minimize the objective function $$\Phi(v) = \|Mv\|_\infty,$$ where $v$ is constrained to be a probability vector, i.e., $v_1+\...
3
votes
0answers
57 views

Levinson Recursion for Non Square Toeplitz Matrices

Given a rectangular Toeplitz Matrix $ H $, how could one solve: $$ y = H x $$ For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $: $$ H = \begin{bmatrix} {h}_{1} & 0 & ...
3
votes
0answers
68 views

Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
3
votes
0answers
134 views

Iteratively solving a sparse, ill-conditioned system

I have a sparse (density = 0.2%), ill-conditioned system that I am trying to solve, with no luck. Background I have a sequence of sampled data, where two of every 8 samples have been zeroed due to a ...
3
votes
0answers
51 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 ...
2
votes
0answers
69 views

Residual of Poisson equation with periodic boundaries

I am trying to write a multigrid solver for Poisson's equation, $-\Delta u=f$, on the unit square, $\Omega=(0,1)^2$ with periodic boundaries. My primary source has been Multigrid by Trottenberg, ...
2
votes
0answers
72 views

Solving a huge least squares system of equations when I can only evaluate Ax

I have a situation where I can generate a system of $M$ linear equations for $N$ variables ($N \ne M$). Implicitly this is of the form $Ax=b$ with $A \in \mathbb{R}^{M \times N}$, although I never ...
2
votes
0answers
127 views

Richardson's Iteration, Gradient Method and Spectral Radius

Richardson's iteration introduce a scalar $\alpha$ to the update formula: $$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)} $$ And compute $\alpha$ by minimizing the spectral radius:...
2
votes
0answers
121 views

Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
2
votes
0answers
86 views

Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
2
votes
0answers
190 views

Iterative linear solvers compatible with automatic differentiation?

I'm using automatic differentiation on a function that contains a sparse nonsymmetric linear system to be solved. I was using BiCGStab to solve this part of the function, but noticed the derivatives ...
2
votes
0answers
53 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 ...
2
votes
0answers
103 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 ...
2
votes
0answers
206 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 ...
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 ...
2
votes
0answers
221 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....
2
votes
0answers
714 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 $...
2
votes
0answers
97 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? ...
2
votes
0answers
122 views

Lapack++ for QR algorithm

I have recently started using Lapack++ which I found convenient for my programming purpose, in general. Now, I need to solve a matrix using QR algorithm. I've searched the user manual and I found a ...
2
votes
0answers
217 views

Is it possible to run a Solver Foundation solver against a model containing linear and non-linear elements?

This is a follow up question to one I made previously about non-linear equations and ranged real numbers in Solver Foundation. I acknowledge that where possible, rewriting a problem that is non-...
1
vote
0answers
51 views

2-norm of solution update suddenly becomes zero after a few iterations

I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
1
vote
0answers
31 views

What kind of problem or matrices are suitable for multigrid method?

For Poisson or Convection-diffusion equation as follows: $$ -\Delta u=f,\qquad u|_\Omega = g. $$ or $$ -\Delta u +\vec{w}.\nabla u=f,\qquad u|_\Omega = g. $$ using FDM or FEM discretization, we can ...
1
vote
0answers
58 views

Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold

Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
1
vote
0answers
61 views

implementation for coppersmith matrix multiplication

Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
1
vote
0answers
45 views

Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines

I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways. One of these claims is that my proposed solution requires no explicit SVD and ...
1
vote
0answers
59 views

Why do higher order finite elements (Q2) do not perform well for large Peclet number flows, as compared to Q1 finite elments?

I a solving the 2d steady state convection-diffusion problem on the famous flow around a cylinder in rectangular domain benchmark. My numerical results show that with Q1 finite elements, the solver is ...
1
vote
0answers
61 views

Parallel dense solve with submatrices from mesh refinement with Petsc

For a Bounday Element Method problem I require the solution of a system of linear equations with multiple right-hand sides. Though this is a dense system, I still want to do it via Petsc in parallel. ...
1
vote
0answers
42 views

Iterative solver, which balances the equations with the biggest errors

I am trying to understand the mathematical side of an algorithm, which approximates the solution of coulomb's law. Their approach is to balance the two elements with the biggest positive/negative ...
1
vote
0answers
234 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: ...
1
vote
0answers
88 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 ...
1
vote
0answers
84 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 ...
1
vote
0answers
56 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_\...
1
vote
0answers
128 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. ...
1
vote
0answers
33 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 ...
1
vote
0answers
575 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
0answers
529 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 ...
1
vote
0answers
256 views

Memory allocation error with GSL ODE solver applied to system of 4 ODEs

I am trying to solve a (large) system of ODEs with GSL solvers. When I use driver method I get an error message of could not allocate space for gsl_interp_accel, ...
0
votes
0answers
39 views

Is there any function to calculate condition number of sparse matrix in Eigen libraray?

The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values. However I need to know condition number of a sparese matrix due to slow computation speed using ...
0
votes
0answers
53 views

The error in SOR algorithm suddenly falls to zero when it reaches 1e-7 range

I am solving the Poisson equation for heterojunction using Fortran90. I use the SOR algorithm to arrive at the potential profile. I see the weird behavior where the error (the difference between the $...