19 votes
Accepted

Why does this preconditioner effectively reduce the condition number of a random SPD matrix?

If the eigenvalues of $A$ are $\lambda_1, \lambda_2, \dots,\lambda_n$, the eigenvalues of $A + \mu I$ are $\lambda_1 + \mu, \lambda_2 + \mu, \dots, \lambda_n + \mu$. It is an easy computation to ...
Federico Poloni's user avatar
15 votes

Why are systems with clustered eigenvalues easy to solve?

A good explanation of this phenomena with many examples is given in Iterative Methods for Linear and Nonlinear Equations by Tim Kelley. The crux of it comes down to the fact that each step of a ...
whpowell96's user avatar
  • 2,443
13 votes
Accepted

How to directly compute the inverse of an ill-conditioned dense matrix

Though it is a relatively rare situation when you actually have to calculate an inverse of the matrix, not all techniques were created equally. I would use the term badly-conditioned instead of ill-...
Anton Menshov's user avatar
  • 8,672
12 votes

Why does this preconditioner effectively reduce the condition number of a random SPD matrix?

The accepted answer is right: you are not making a preconditioner. To elaborate. For a matrix $A$, a preconditioner is a matrix $B$ such that $B^{-1}A$ has a smaller condition number than $A$. The ...
Victor Eijkhout's user avatar
10 votes
Accepted

Poorly conditioned, easily evaluated sum for unit testing

The condition number of sum $s(x) = \sum_{j=1}^n x_j$ is given by $$ \kappa(x) = \frac{\sum_{j=1}^n |x_j|}{|\sum_{j=1}^n x_j|} = \frac{s(|x|)}{|s(x)|}$$ and reflects the sums sensitivity to small ...
Carl Christian's user avatar
8 votes
Accepted

Why can ill-conditioned linear systems be solved precisely?

Added after my initial answer: It appears to me now that the author of the referenced paper is giving condition numbers (apparently 2-norm condition numbers but possibly infinity-norm condition ...
Brian Borchers's user avatar
8 votes
Accepted

Matrix condition number and reordering

No. A reordering of a matrix $\boldsymbol{A}$ is equivalent to conjugation by a permutation matrix $\boldsymbol{P}$. In other words, the reordered matrix can be written as $\boldsymbol{A}_r = \...
cdipaolo's user avatar
  • 402
8 votes

Why are systems with clustered eigenvalues easy to solve?

At the $k$th iteration, typical Krylov methods for solving $Ax=b$ (such as CG, MINRES, and GMRES) implicitly construct a $k$th order polynomial $Q(x)$ such that: $Q(0) = 1$. $|Q(\lambda_i)|$ is as ...
Nick Alger's user avatar
  • 3,143
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
6 votes
Accepted

Why $\alpha I +A$ can improve the condition nubmer of a SPD matrix $A$?

The inequality $\frac{\alpha + \lambda_{max}(A)}{\alpha+\lambda_{min}(A)} > \frac{\lambda_{max}(A)}{\lambda_{min}(A)}$ doesn't hold because $\lambda_{max}(A) > 1 > \lambda_{min}(A) > 0$ ...
Tihskirap Ayayhdapu's user avatar
6 votes
Accepted

Is large condition number good measure of nearness to singularity for a matrix?

The condition number measures the relative distance from singularity of a matrix $A$: that is, $$ \min_{\text{$X$ is singular}} \frac{\|A-X\|}{\|A\|} = \frac{1}{\kappa(A)} $$ (the norm here is the ...
Federico Poloni's user avatar
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

Condition number of $X^{T}AX$

Let's show that we cannot bound the condition number of $X^T A X$ by using only the condition number of $A$ and the norm of $X$. Let $A=I$, so its condition number is exactly $1$. Let $X$ consist of ...
hardmath's user avatar
  • 3,359
6 votes
Accepted

Is there a general threshhold for which a large condition number becomes "problematic?"

This answer is my comments compiled and edited together. I apologize for the repetition. I would consider anything above $1/\sqrt{\epsilon_{\text{mach}}}$ problematic, so it would be floating point ...
Abdullah Ali Sivas's user avatar
6 votes

Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?

The condition number of a root $r$ of a polynomial $p$ is $$ \kappa := \frac{\left\| p \right\|}{|rp'(r)|} $$ There is some arbitrariness in the choice of norm which affects the definition of the ...
user14717's user avatar
  • 2,155
5 votes

Large condition number with good accuracy

Of course you can. The condition number gives you an upper bound for the error. Suppose you want to solve $Ax=b$ where $A$ is a matrix with large condition number. The error depends on the structure ...
Gil's user avatar
  • 382
5 votes
Accepted

Missing something fundamental about condition number estimation

This algorithm is most useful for two situations, which are related to each other in practice: You don't know the matrix entries explicitly, but instead can only compute matrix-vector products with ...
Reid.Atcheson's user avatar
5 votes

Ill-condioned Linear System and Gaussian Elimination

Ill conditioning is a property of the system of equations rather than the algorithm used to solve the system of equations. Using a bad algorithm can certainly make the situation worse, but you're ...
Brian Borchers's user avatar
5 votes

How to Invert a Poorly Conditioned Matrix

There is no simple fix. For an ill-conditioned matrix $A$, the harm (loss of precision) is already done the moment you wrote those numbers in a numpy array, because that tiny $10^{-16}$ perturbation ...
Federico Poloni's user avatar
4 votes

Sparse least squares with a (black-box) ill-conditioned operator

There's no reason to compute elements of $M=A^{*}A$ here. You will need the ability to compute the adjoint operator $z \rightarrow A^{*}z$. With that, you can use a matrix-free iterative least-...
Brian Borchers's user avatar
3 votes

CHOLMOD condition number estimate

This question is covered in the following paper: N. J. Higham, "A survey of condition number estimation for triangular matrices," SIAM Review, vol. 29, no. 4, pp. 575–596, Dec. 1987. Also available ...
Anton Menshov's user avatar
  • 8,672
3 votes
Accepted

Accurately Computing a Positive Vector in the Nullspace of a Matrix

Quick answer to summarize my comments. Keep in mind that a delicate point is the choice of the truncation threshold in the SVD (what is "numerically zero" and what is not). If you do not ...
Federico Poloni's user avatar
3 votes
Accepted

Conjugate gradient - ill-conditioning and numerical tolerance

Let $x$ denote the solution of $Ax=b$ and let $\hat{x}$ denote the computed solution. We cannot hope to do better than $$\hat{x} = \text{fl}(x),$$ i.e., the floating point representation of $x$. In ...
Carl Christian's user avatar
3 votes
Accepted

Numerical method for solving a system with positive definite blocks

Please notice that you assumptions do not preclude singular matrices. A specific example is \begin{equation} C = \begin{bmatrix} I & I \\ I & I \end{bmatrix} \end{equation} where $I$ denotes ...
Carl Christian's user avatar
3 votes

Condition Number of Rectangular Matrices

I guess I figured out the answer to my question. Suppose the SVD of $A = U \Sigma V^\ast$ (where $V^\ast$ is the conjugate transpose of the matrix $V$). Noting the fact that the unitary ...
gpavanb's user avatar
  • 572
3 votes

Condition number of a matrix

There are different "matrix condition numbers" relative to the problem to be solved. I assume that you are inquiring about the matrix condition number to solving a linear system $Ax = b$. The ...
GertVdE's user avatar
  • 6,179
2 votes

Condition number of two perburbation matrix regarding limit and quadtrature integration rules

1. For a matrix $A$ with distinct eigenvalues, adding a perturbation $\delta A$ results [1] in a change to eigenvalues of magnitude (to first order) $$ \delta\lambda_i = (X^{-1}\delta A X)_{ii}, $$ so ...
Kirill's user avatar
  • 11.4k
2 votes
Accepted

Condition number of matrix and effects of round off errors

For sparse matrices $A$, that are a discretized version of operators in PDEs in FE, FV, or FD, you do know your sparsity pattern before you compute the actual entries. So, you usually compute matrix ...
Anton Menshov's user avatar
  • 8,672
2 votes
Accepted

Defining a condition number and termination criteria for Newton's method

Any reasonable convergence criterion must be invariant to scaling of the function. A decent stopping criterion is therefore if $\|f(x_k)\|≤ \epsilon\|f(x_0)\|$ where $x_0$ is the starting point of the ...
Wolfgang Bangerth's user avatar
2 votes

Assessing numerical error in solving a least squares problem

I think most solvers will give you a residual error. If you flip your equation to read: $Ax - b = r\approx 0$ The solver will usually provide you with the residual error like: $|r|$. Now if you ...
MPIchael's user avatar
  • 2,935

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