26

Yes, the condition number always matters in floating-point arithmetic, whether you choose to solve your system with an iterative or direct method. The relative accuracy of an approximate solution to $Ax = b$ obtained from LU factorization with pivoting is $O(\kappa(A) \cdot \varepsilon)$, where $\varepsilon$ is the smallest floating point number such that $1 ...


13

You can use additive $$ P_a^{-1} x = (B^T B)^{-1} x + (C^T C)^{-1} x, $$ multiplicative $$ P_m^{-1} x = (B^T B)^{-1} x + (C^T C)^{-1} \Big(x - A (B^T B)^{-1} x \Big), $$ or symmetric multiplicative. Methods of this class are available in PETSc using PCCOMPOSITE in PETSc. For example, petsc/src/ksp/ksp/examples/tutorials$ ./ex2 -m 100 -n 100 -...


12

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-conditioned. For badly conditioned matrices, you might opt in the SVD-route to calculate the inverse: $$ A=U\Sigma V^H \implies A^{-1}=V\Sigma^{-1}U^H. $$ If ...


9

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 changes in the input. Specifically, we have $$ \underset{\epsilon \rightarrow 0_+}{\lim}\sup \left\{ \frac{1}{\epsilon} \left|\frac{s(x+\Delta x) - s(x)}{s(x)} \...


8

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 numbers) in the table while giving maximum absolute errors rather than norm relative errors or maximum elementwise relative errors (these are all different measures.) ...


8

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 = \boldsymbol{P}\boldsymbol{A}\boldsymbol{P}^*$ and $\boldsymbol{A}_r^{-1} = \boldsymbol{P}\boldsymbol{A}^{-1}\boldsymbol{P}^*$. Since the spectral norm is unitarily ...


7

The simplest/fastest way to solve ill-conditioned problems is to increase precision of computations (by brute force). Another (yet not always possible) way is to re-formulate your problem. You might need to use quadruple precision (34 decimal digits). Even though 20 digits will be lost in a course (because of condition number) you will still get 14 correct ...


6

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 an invertible diagonal block with $p$ rows of zeros padded at the bottom: $$ X = \begin{pmatrix} D \\ 0 \end{pmatrix} $$ Now $X^T A X = D^2$, and its ...


6

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 Euclidean / induced / spectral norm --- i.e., $\|A\|=\sigma_1(A)$). This property follows from the Eckart-Young theorem. Your example with a small $\|A\|$ ...


6

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})$ where the exponent equals the order of the differential operator. As a consequence, if you just make the mesh fine enough, you can make the condition number ...


6

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$ and $\alpha > 0$. In fact, the reverse inequality holds in this case. Hence, there is no contradiction here. EDIT: From the comments, I realized that the ...


6

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 system dependent. But it also depends on the size of the linear system. You can create small linear systems (3x3) with a condition number at O(1000) and the ...


5

No, a different unit will not alter the condition of the system. Say your FEM system is $$ Au + \beta Mu = 0. \quad (*) $$ Then the parameter $\beta$, here something like $b/a$ from your example, will depend on the units in a way that only allows you to add "$A$" and "$M$" in terms of units. A rescaling will then mean a multiplication of $(*)$ by a constant ...


5

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 of $A$ and on $b$. As an example, if $A$ is a $2 \times 2$ diagonal matrix, with elements $1$ and $10^{-20}$, solving $Ax=b$ will still be accurate, despite ...


5

Your question really doesn't admit a simple answer- we need to know more specifics about your problem to provide a useful answer. In general, iterative methods can be faster than direct factorization for large sparse systems of equations if the system is reasonably well conditioned or if it is badly conditioned but you have a good preconditioner or if you ...


5

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 the matrix (often called "matrix-free") You want the 1-norm for the inverse of a matrix. The inverse of a sparse matrix is typically dense, and since sparse ...


5

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 already in trouble when you try to solve an ill-conditioned system of equations with A coefficients or right-hand side b with even tiny errors even if you use ...


5

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 from the exact non-representable values is already harmful. You could increase your working precision; but at that point the question is if your matrix entries $...


3

You can get a rough estimation of the condition number using the Gershgorin circle theorem. This article in Wikipedia has a nice explanation: http://en.wikipedia.org/wiki/Gershgorin_circle_theorem For a complex matrix $A$ of size $n\times n$, its n Gershgorin circles are drawn in the complex plane, the center of the circles are $a_{ii}$, the radius of the ...


3

Estimates can be obtained from Krylov subspace methods, such as GMRES, and PETSc has functionality for that. For a symmetric matrix, the 2-norm condition number is the spectral condition number, and there exist algorithms to estimate the 2-norm condition number, so if you really do want the condition number for your unpreconditioned matrix, you can use ...


3

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 the identity matrix of dimension $I$. This example also shows that the condition that $B$ is positive definite is not necessarily useful. I appreciate the fact ...


3

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 transformations $U$ and $V$ preserve the 2-norm, $\|Ax\|_{2}$ for any unit vector $x$ can be written as \begin{align*} \frac{\|Ax\|_{2}}{\|x\|_{2}} = \|Ax\|_{2} &= \|U ...


3

As of version 3.2, PETSc supports sparse quad-precision computations on gcc/gfortran 4.6 and newer. You'll need a quad-precision BLAS and LAPACK, which PETSc can provide to you (along with quad support) with the following (partial) configure command: ./configure --with-precision=__float128 --download-f2cblaslapack See the FAQ for a little more ...


3

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 condition of a problem is a measure for the sensitivity of the solution on small perturbations in the problem statement. Using the approachin "Matrix Computations, ...


3

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 see a clear drop in the singular values, then it means your precision is insufficient to identify zeros. Since $\|Ax\|_\infty / \|A\|_\infty \|x\|_\infty$ is of ...


2

Ill-conditioned systems are better solved by regularisation than by increasing the numerical precision. Search for "regularisation ill-posed" for the gory details.


2

I might give the Trilinos library a try. They have templated sparse matrix libraries under Tpetra (which is supposed to replace Epetra, their original sparse matrix library). You can template double, complex, quad, etc, and they have possibly the largest selection of solvers (both direct and iterative) next to PETSc. Edit: after reading the comments, the ...


2

No. It is the ratio of the scales of these two operators that will drive the condition number not their absolute magnitude. You can multiply the whole equation through by any arbitrary constant without changing the condition number.


2

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 $|\delta \lambda_i| \leq \kappa(X)\|\delta A\|$. The change in condition number $\kappa(A)$ is then given by $$ \delta(\kappa(A)) = \kappa(A)\big(\delta(\log \...


2

tl;dr They reported a condition number, not necessarily the right condition number for the matrix, because there is a difference. This is specific to the matrix and the right hand side vector. If you look at the documentation for *getrs, it says the forward error bound is $$ \frac{\|x-x_0\|_\infty}{\|x\|_\infty} \lesssim \mathrm{cond}(A,x)u \leq \mathrm{...


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