# Tag Info

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

Solving a (linear) PDE consists in discretizing the equation to yield a linear system, which is then solved by a linear solver whose convergence (rate) depends on the condition number of the matrix. Scaling the variables often reduces this condition number, thus improving convergence. (This basically amounts to applying a diagonal preconditioner, see ...

9

PDEs of which the solutions have sharp boundaries pose problems that go beyond being able to represent the solution in floating point. This is especially true when solutions have a certain physical meaning, e.g., a density (that per se cannnot be smaller than 0). Consider, for example, $$-\varepsilon \Delta u + u = 0 \text{ on } \Omega,\\ u = 1 \text{ on } \... 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

No, Jacobi only ever corrects relative scales. It does nothing for "smooth" ill-conditioning, such as the $\kappa(A) \in O(h^{-2})$ asymptotics for second order elliptic problems. If you are using a Krylov method, the global scale is automatically corrected, but with a stationary iteration, the (constant) scaling is needed somehow (could just be in the ...

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

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

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

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 Please notice that you assumptions do not preclude singular matrices. A specific example is $$C = \begin{bmatrix} I & I \\ I & I \end{bmatrix}$$ 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$xcan be written as \begin{align*} \frac{\|Ax\|_{2}}{\|x\|_{2}} = \|Ax\|_{2} &= \|U ... 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 matrixA$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 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

Dealing with floating point numbers can be trick with regards to subtraction of small numbers from larger numbers, as well as with many other aspects. I would recommend reading John D. Cooks blog posts on them, such as Anatomy of a Floating Point Number as well as Oracle's What Every Computer Scientist Should Know About Floating-Point Arithematic Also ...

2

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

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