Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
15 votes
Accepted

What is this regularization technique?

All they are doing is taking the problem of minimizing $x^T x$ subject to $A x = b$ and then forming a Lagrangian, like so: $$L(x, \lambda) = x^T x + \lambda^T (A x - b)$$ From here, you want to find ...
spektr's user avatar
  • 4,248
13 votes
Accepted

When do not use preconditioners for sparse linear system of equations?

In my experience, you always need (or better use) some form of preconditioning. The type and complexity of the precondition would vary depending on the task though. From Y. Saad, Iterative Methods for ...
Anton Menshov's user avatar
  • 8,672
12 votes
Accepted

Without positive definiteness, does an iterative solver work?

No, positive definiteness (and symmetry) are only precondition to using the Conjugate Gradient method. But there are plenty of other iterative methods such as MinRes and GMRES that can be used for ...
Wolfgang Bangerth's user avatar
9 votes

Is it really necessary to solve a system of linear equations in the Finite Element Method?

I think your question is actually pretty fundamental and deserves a thoughtful answer. Paraphrasing a bit, your question is perhaps motivated by the observation that engineering design is often ...
rchilton1980's user avatar
  • 4,896
8 votes
Accepted

What is the **contraction factor and convergence factor** of a iteration method?

These concepts are related. Let $A = M - N$ and consider the iteration $$ M x_{k+1} = N x_k + b. $$ We can write this as a mapping $\Phi : \mathbb{R}^n \to \mathbb{R}^n$ defined by $$ \Phi(y) = M^{-1}(...
Will P.'s user avatar
  • 831
8 votes
Accepted

Using matrix exponential to solve linear system

You are effectively asking how to compute $y=(\log M )^{-1}b$, where $M=e^A$ is the given matrix. There are several methods for computing $f(M)b$ without forming $f(M)$, and they are reviewed here. ...
Amit Hochman's user avatar
  • 1,081
7 votes
Accepted

Why do not we choose the error solution norm as an iterative method's criterion?

We can't use the criterion you show last in practice because it requires us to know what $\kappa(A)$ is. But computing the condition number is, in general, more expensive than solving a linear system. ...
Wolfgang Bangerth's user avatar
7 votes

Solution of the linear system using Sherman-Morrison formula for 1000000x1000000 (7450.6GB) matrix using MATLAB

As Federico has mentioned, you probably don't want to deprive yourself of the learning experience. I'll just give you a small nudge in the right direction. You will never be able to store $A$. You ...
Thijs Steel's user avatar
  • 1,723
7 votes

Correctness of direct numerical solution of ill-conditioned linear system

One thing you can do to test it is computing the residual $b - A \tilde{x}$ in higher precision. If the residual is small (and this will always happen with an accurate solution), then you can testify ...
Federico Poloni's user avatar
7 votes

What is this regularization technique?

I have never seen it used for underdetermined systems, but for overdetermined systems (tall thin $A$) the version obtained replacing $A$ with $A^T$ in your block matrix a common reformulation, known ...
Federico Poloni's user avatar
6 votes
Accepted

Fastest way to solve a sparse unsymmetric system many times

Generally speaking, for many right-hand side (RHS) problems, a direct solver is a more feasible solution for several reasons: Major computations are performed during the factorization step (which is ...
Anton Menshov's user avatar
  • 8,672
6 votes
Accepted

Is steady linear elasticity inherently ill-conditioned?

The condition number for the stiffness matrix of any method (finite elements, finite volumes, finite differences) applied to a second order differential operator always grows as ${\cal O}(h^{-2})$ ...
Wolfgang Bangerth's user avatar
6 votes
Accepted

Solving for a vector in a linear system that is both left and right multiplied

Your second term is linear in $x$, so it can be rewritten as $Cx$ where $C$ is a suitable $n\times n$ matrix. You just need to figure out what its entries $C_{ij}$ are: for this you need a little ...
Federico Poloni's user avatar
6 votes

Solving for a vector in a linear system that is both left and right multiplied

Based on Federico's answer, I think you can easily figure out what are $C_{ij}$ entries by explicitly writing the second term ($Bxv$) as: $$(Bx)_{ij} = \sum_{\alpha=1}^{n} B_{ij\alpha} x_{\alpha}$$ $...
Mithridates the Great's user avatar
6 votes
Accepted

Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular

It's a complicated question, which is why I've recorded a whole bunch of video lectures on the topic :-) Take a look at lectures 34 and following here: https://www.math.colostate.edu/~bangerth/videos....
Wolfgang Bangerth's user avatar
5 votes
Accepted

Why Krylov subspace iterative methods are faster than classical iteration?

I must admit I never actually checked all the details myself, but I think that's a sketch of the general idea. The $k$th iterate $x_k$ produced by Richardson iteration lies in the Krylov subspace $...
Federico Poloni's user avatar
5 votes
Accepted

How to verify solution to pre-conditioned linear systems solver?

You've started with a singular linear system of equations $Ax=b$. As a practical matter, it's unlikely that $b$ lies exactly in the range of $A$, so at best you can find a least squares solution that ...
Brian Borchers's user avatar
5 votes
Accepted

How "sparse" should a sparse matrix be to see benefits?

This kind of scaling is fairly common and sparse direct factorization methods are commonly used on matrices of up to a few hundred thousand rows and columns. By the time you get to $N=20$, you’ll ...
Brian Borchers's user avatar
5 votes
Accepted

How to implement flexible gmres in matlab?

First of all, MATLAB's gmres assumes that the preconditioner you use is linear. This is important! Actually it is the main difference between FGMRES and GMRES. ...
Abdullah Ali Sivas's user avatar
5 votes
Accepted

Solving $(I-Q)x={\bf 1}$ for sub-stochastic sparse $Q$ of dimension 5M $\times$ 5M

Yea, iterative solvers are often more effective for sparse problems, as long as the condition number isn't too large. IterativeSolvers.jl provides several common methods. The general recommendation ...
Neil Lindquist's user avatar
5 votes

What is this regularization technique?

Spektr's answer is already great but note that you can also argue about this in the following manner $2x + A^T \tau = 0$ and $Ax=b$ implies that $x = -\frac{1}{2} A^T\tau$ and plugging it in the ...
lightxbulb's user avatar
  • 2,162
4 votes

Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights

Michael Saunders wrote a sparse LU package that can do rank-1 updates, LUSOL. You could try to use that, since you write that direct solvers are viable for your problem.
Federico Poloni's user avatar
4 votes

Solve $Ax=b$ repeatedly where $A$ is a sparse weighted Laplacian matrix with changing weights

It appears to me that you are dealing with a sequence of linear systems $A_j x_j = b$, where $A_{j+1}$ is a low rank modification of $A_{j}$. In your case, I would investigate if the Krylov subspace $...
Carl Christian's user avatar
4 votes

How to obtain linear tridiagonal system from PDE

Welcome to the site. You are actually virtually finished, but may not have realised it yet. A tridiagonal linear system is another name for a matrix problem which only has non zero entries on the ...
origimbo's user avatar
  • 2,249
4 votes

Why OpenFOAM uses its own data structures and linear solvers?

In the light of more recent information: OpenFOAM follows the C++11 standard without any exception at the time of writing. Therefore, you can use any C++ containers of this standard within OpenFOAM. ...
Herpes Free Engineer's user avatar
4 votes
Accepted

Solving an m x m symmetric linear system involving a matrix multiplication versus an (n+m) x (n+m) system

In my opinion, you need a really good excuse to take a symmetric positive definite system and then turn it into an indefinite system. The first thing I would try is the conjugate gradient method ...
Charlie S's user avatar
  • 661
4 votes
Accepted

1D FEM for nonlinear diffusion coefficient

You would need to linearize the problem. I prefer to do it before discretization but it's possible to do also after discretization. (I'm a bit skeptical of linearization after discretization because I ...
knl's user avatar
  • 2,104
4 votes

Algebraic multigrid as solver and as preconditioner

Most people use (algebraic as well as geometric) multigrid as preconditioners these days. It's an empirical observation that that leads to faster convergence in terms of iterations, given that in a ...
Wolfgang Bangerth's user avatar
4 votes

Simplest solver for linear equation systems

I'd recommend a BLAS1/2-style implementation of LU decomposition with partial pivoting, along with forward/backward triangular solves. If you only have single digit numbers of unknowns, it should be ...
rchilton1980's user avatar
  • 4,896
4 votes

Interpolation and Restriction operators in Multigrid

It's fundamentally because if you have that $A^h$ is a symmetric matrix, you want that $A^{2h}=P^TA^hP$ is also a symmetric matrix. You want this because you want to again use the same kind of ...
Wolfgang Bangerth's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible