Questions tagged [condition-number]

The tag has no usage guidance, but it has a tag wiki.

Filter by
Sorted by
Tagged with
29
votes
2answers
12k views

Does a tiny determinant imply ill-conditioning of a matrix?

If I have a square invertible matrix and I take its determinant, and I find that $\det(A) \approx 0$, does this imply that the matrix is poorly conditioned? Is the converse also true? Does an ill-...
15
votes
3answers
1k views

Is variable scaling essential when solving some PDE problems numerically?

In semiconductor simulation, it is common that the equations are scaled so they have normalised values. For example, in extreme cases electron density in semiconductors can vary over 18 order of ...
15
votes
2answers
499 views

Is there any way to do "double preconditioning"

Question: Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$: $$A \approx B^TB$$ and $$A \approx C^TC,$$ where the inverses of the factors $B, ...
14
votes
3answers
6k views

What are the symptoms of ill-conditioning when using direct methods?

Suppose we have a linear system and we know nothing about its conditioning and have no preliminary information about the solution. We blindly apply Gaussian elimination and obtain some solution $x$. ...
13
votes
1answer
928 views

Are direct solvers affected by the condition number of a matrix?

If I were to solve a relatively small problem, that is, a problem that can be handled by a direct method like LU, then does the condition number of the linear operator affect the accuracy of the ...
13
votes
2answers
1k views

Why can ill-conditioned linear systems be solved precisely?

According to the answer here, large condition number (for linear system solving) decreases the guaranteed number of correct digits in the floating point solution. Higher order differentiation matrices ...
10
votes
4answers
485 views

Are there any quad-double arithmetic sparse matrix package?

I am working on some ill-conditioned large sparse linear system of equations. I want to use double-double arithmetic or quad-double arithmetic to solve them. I know that there is a package named MPACK ...
9
votes
3answers
5k views

Solving a sparse and highly ill-conditioned system

I intend to solve Ax = b where A is complex, sparse, unsymmetric and highly ill-conditioned (condition number ~ 1E+20) square or rectangular matrix. I have been able to solve the system with ZGELSS in ...
9
votes
4answers
3k views

Condition number of A'A and AA' formulations

It's shown (Yousef Saad, Iterative methods for sparse linear systems, p. 260) that $cond(A'A) \approx cond(A)^2$ Is this true for $AA'$ as well? In case $A$ is $N\times M$ with $N \ll M$, I observe ...
9
votes
3answers
4k views

Fastest algorithm to compute the condition number of a large matrix in Matlab/Octave

From the definition of condition number it seems that a matrix inversion is needed to compute it, I'm wondering if for a generic square matrix (or better if symmetric positive definite) is possible to ...
9
votes
1answer
7k views

How to approximate the condition number of a large matrix?

How do I approximate the condition number of a large matrix $G$, if $G$ is a combination of Fourier transforms $F$ (non-uniform or uniform), finite differences $R$, and diagonal matrices $S$? The ...
8
votes
1answer
125 views

Preconditioning and effects on precision of solution of LSE

In my courses on numerical analysis, I have been taught that the main and principal motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers ...
7
votes
4answers
2k views

precision vs matrix condition number

I have an application in which I am computing a quantity which is approximated by an average over $M$ points. In theory, the average converges to the correct quantity when $M$ is infinite. In practice,...
7
votes
1answer
779 views

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

I know that it is generally a bad idea to compute the inverse matrix directly. However, if it is necessary to compute the inverse of an ill-conditioned invertible dense matrix, then what can I try? ...
7
votes
2answers
964 views

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

I am new to numerical linear algebra, so i came to know that condition number in 2-norm case will be ratio of largest to smallest singular value. Another concept "Nearness To Singularity" is measured ...
7
votes
1answer
605 views

Jacobi preconditioner not reducing condition number?

Let's say you have a general matrix $A$, with diagonal entries $a_{ii} = d>0$. (No assumptions are made about the off-diagonal elements.) Then Jacobi preconditioning doesn't improve condition ...
7
votes
0answers
126 views

"Geometry of ill-conditioning" for least-squares problems

It is an idea that dates back to Demmel, 1987 that the condition number of a problem is often related to the distance to the closest ill-posed problems. In Section 3 of the above paper, the author ...
6
votes
1answer
508 views

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

The condition number of function evaluation $$ \mathrm{cond}(f,x) := \left| \frac{x f'(x)}{f(x)} \right| $$ is infinite at a root of $f$. Hence it is useless for rescaling a tolerance which defines an ...
5
votes
2answers
253 views

Imposing invertibility on a Matrix

I have a symmetric positive semidefinite covariance matrix $A$, which is approximately computed as the output of a quadratic regression. I then need to invert $A$, but often it is close to singular. I'...
5
votes
2answers
250 views

Condition number of (A + cI) matrix

For given matrix $A \in R^{n\times n}$, identity matrix $I$ and constant $c > 0$ is this possible to express $cond(A + cI)$ knowing $cond(A)$ and $c$?
5
votes
2answers
908 views

Condition number from incomplete Cholesky factorization

I'm having difficulties patching together from what I read about obtaining the condition number of a real, symmetric, positive definite sparse matrix. In my code, I found that there is incomplete ...
5
votes
1answer
115 views

Accurately Computing a Positive Vector in the Nullspace of a Matrix

I'm sure this question has been asked before yet after many hours of searching I am unable to find a definitive answer. The problem at hand is solving the linear system: $$A \mathbf{x} = \mathbf{0}$$ ...
5
votes
1answer
384 views

CHOLMOD condition number estimate

The CHOLMOD library provides a CHOLMOD_rcond function that estimates the reciprocal condition number (in the one norm) of a symmetric positive definite matrix from ...
4
votes
2answers
216 views

Problem Condition and Algorithm Stability

Consider 2 mathematical problems: $$ f_1(x) = a - x \\ f_2(x) = e^x -1 $$ The condition number for a function is defined as follows: $$ k(f) = \left| x \cdot \frac{f'}{f} \right| $$ Lets analyze ...
3
votes
1answer
197 views

Matrix condition number and reordering

Does the condition number change when a matrix is reordered by e.g. Cuthill Mckee or some other method?
3
votes
2answers
228 views

Does length unit in FEM affect numerical condition?

I try to solve a system of coupled PDEs using FEM. Unfortunately, the originating matrix has very poor condition. After days of double checking and thinking, I suspect the following reason: Given a ...
3
votes
1answer
126 views

Condition number of $X^{T}AX$

$A$ is a symmetric matrix and is known to be invertible. $X$ is rectangular of size $(N+p) \times N$ with $p > 0$ but full column rank. Can we provide an upper bound on the condition number of $X^...
3
votes
1answer
304 views

Closed form for singular values of 2D Laplacian?

Does anyone know where to find an analytic form for the singular values of the finite-difference approximation to the 2D Laplacian, expressed in matrix form for a square grid? This would be for the ...
3
votes
1answer
1k views

Non-linear root finding when the Jacobian is almost singular

I'm trying to solve a system non linear-equations: $$ \frac{\partial K(\mathbf{\lambda})}{\partial \lambda_i} - c_i = 0 $$ for $i = 1, \dots, 15$, using Newton's method: $$ \lambda^{k + 1} = \lambda^k ...
3
votes
2answers
52 views

Is "sensitivity" a term in numerical computation?

The section 4.2 "Poor Conditioning" in the book Deep Learning defines the condition number of the function $f(x) = A^{-1}x$ as \begin{align} \underset{i,j}{\max}~ \Bigg| \frac{\lambda_i}{ \...
3
votes
1answer
526 views

Condition number of an algorithm

I am stuck with a problem about finding the condition number of an algorithm. I tried to find an example, but i couldn't. Can anybody help me, please? Given is $f(x)=\ln(x)$. We have the algorithm $...
3
votes
2answers
67 views

Parameter Fitting: Need measure of data 'support' for a parameter solution

I am estimating parameters on a dataset that would, for the most part, result in a weakly constrained solution. The dataset however also contains a few more data points that make the solution well-...
3
votes
1answer
353 views

Designing a preconditioner for a very Ill-conditionned matrix

I am a physicist with limited numerical methods knowledge and I am trying to speed up the inversion of a very ill-conditioned problem ($rcond>10^{30}$). The same sparse square matrix is used ...
2
votes
1answer
154 views

Poorly conditioned, easily evaluated sum for unit testing

I am looking for examples of poorly conditioned sums which can rapidly be evaluated, for the purposes of unit testing. I'm currently using the series representation for $\ln(2)$: $$ \sum_{n=1}^{\...
2
votes
2answers
563 views

Ill-conditioned Gram Matrix Assembly

I'm trying to find the best approximation to the function $e^x$ in the finite dimensional polynomial space $P_4$ with respect to the standard basis vectors $B=\{1,x,x^2,x^3,x^4\}$ with inner product $$...
2
votes
1answer
88 views

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

I think the answer is probably no in the linear algebra community, but I'd say anything above $10^8$ and you're starting to lose too much precision, making the situation problematic. In some ...
2
votes
1answer
132 views

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

For Poisson equation with Dirichlet boundary conditions in 2 dimension: $$ -\Delta u=f, $$ using FDM (centered difference) or FEM discretization, we can obtain a SPD system of linear equations as ...
2
votes
1answer
138 views

Is steady linear elasticity inherently ill-conditioned?

Compared to the transient PDE for linear elasticity, the steady equations appear to less well-conditioned. Are they inherently ill-conditioned without the transient term? The condition number for ...
2
votes
1answer
160 views

How to Invert a Poorly Conditioned Matrix

In my research, I need to invert a Fisher matrix in order to get a covariance matrix for me to do parameter estimation. Unfortunately, the values of Fisher matrix vary by many orders of magnitude, and ...
2
votes
1answer
186 views

Ill-condioned Linear System and Gaussian Elimination

Suppose that I have a linear system $Ax=b$ such that $A$ is ill-conditioned. Can I say that it is dangerous to find a solution with Gaussian Elimination for this system, or does there exist some class ...
2
votes
1answer
204 views

Condition Number of Rectangular Matrices

The 2-norm condition number can be easily extended to rectangular matrices. I'm wondering if the inequality for the product of matrices still holds in that case, i.e., $\operatorname{cond}(AB) \leq \...
2
votes
1answer
524 views

Polynomial Regression using Semidefinite Programming

I'm trying to design the frequency response function for a low-pass filter. I need the function to be polynomial and to fulfill the following constraints: the coefficients must sum to 1, the function ...
2
votes
1answer
91 views

Assessing numerical error in solving a least squares problem

I have a linear system of the type $$Ax = b$$ I want to minimise $|b - Ax|^2$. I know there are different approaches to directly solve the system (Normal equation + Cholesky, QR decomposition, SVD ...
2
votes
1answer
256 views

Condition number of matrix and effects of round off errors

In my numerical linear algebra class, I learned that for some matrices, it could have an element that is a very small number that is approximately 0 (and many orders of magnitude different from all ...
2
votes
1answer
516 views

Methods for solving rectangular, full-rank systems of equations -- which is best?

Suppose I have a large, sparse, $m \times n$ matrix $A$, with $m \gt n$ and $\text{rank}(A) = n$. I wish to solve $Ax=b$. Suppose I know that $A$ has the following characteristics: $A$ is somewhat ...
2
votes
1answer
2k views

Solving linear systems with ill-conditioned matrices

As per suggestions of the people from MathOverflow, I'm reposting my question here: I'm currently trying to solve a linear system $Ax = B$, where the matrix $A$ is ill conditioned (i.e. nearly ...
2
votes
0answers
77 views

Regularisation of ill-conditioned matrix-vector problem

I have a linear* problem which arises from an integro-differential system, and writes: $$ (\mathbf{I}+\lambda \mathbf{A})x = b $$ where $\mathbf{A}$ is a real full matrix, size $n\times n$, but is not ...
2
votes
0answers
53 views

How to classify chaotic systems from a stability perspective

I am wondering what chaotic systems are from the perspective of numerical analysis. I am talking about 'deterministic chaos' such as for instance the 'logistic map' exhibits it. That is, the solution ...
1
vote
1answer
79 views

Missing something fundamental about condition number estimation

In Higham's Accuracy and Stability of Numerical Algorithms, Chapter 15, algorithm 15.3 and 15.4: The topic is ostensibly condition number estimation, but these algorithms show how to compute $\gamma$ ...
1
vote
2answers
301 views

Condition number of a matrix

I saw some definition that if $$M=\max_{x\not=0} \tfrac{\|Ax\|}{\|x\|} \quad\text{and}\quad m=\min_{x\not=0} \tfrac{\|Ax\|}{\|x\|} \,,$$ the condition number of $A=M/m$. In my opinion, If we have a ...