Questions tagged [condition-number]
For questions about calculating or interpreting condition numbers. Most commonly refers to the condition number of a matrix, but can be applied generally to analyzing the error in a function based on error in the input.
66
questions
12
votes
2
answers
2k
views
Why are systems with clustered eigenvalues easy to solve?
I came across the following slide by Theo Diamandis & Zachary Frangella on what makes the linear system $Ax=b$ easy to solve using the conjugate gradient method.
Transcription:
CG converges ...
- 2,273
8
votes
0
answers
281
views
Stable alternatives to "condition number"?
A number of numerical problems are easy to solve when condition number $\kappa$ of the problem is low. For instance, conjugate gradient descent complexity scales as $O(\sqrt{\kappa})$.
However
"...
- 2,273
1
vote
1
answer
110
views
Conditioning and Stability of generalized eigenvalue problem
The (generalized) eigenvalue problems with a multiple eigenvalue are the ill-posed ones.
I have two questions that should be simple for experts:
(1) Is the eigenvalue problem much more sensitive to ...
- 113
3
votes
1
answer
226
views
Correctness of direct numerical solution of ill-conditioned linear system
To what extent can you put trust in a numerical solution obtained by direct solver for an ill-conditioned linear system? In other words, how can you test the solution? Dropping it into the system says ...
3
votes
2
answers
861
views
Why does this preconditioner effectively reduce the condition number of a random SPD matrix?
Consider some randomly generated matrix $B\in\mathbb{R}^{100\times100}$ and let $A:=BB^{\top}$
On MATLAB I computed the condition number of $A$, I obtained a value of $2.8377\mathrm{e}+04$
However if ...
- 133
4
votes
1
answer
109
views
Sparse least squares with a (black-box) ill-conditioned operator
It was suggested on math.stackexchange.com that I try to ask this question here.
Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert ...
- 149
4
votes
1
answer
297
views
Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?
I know that NumPy has linalg.cond(A) to find the condition number of a matrix A. But, if I want to find the condition numbers of the roots of a large polynomial ...
- 41
2
votes
0
answers
110
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 ...
- 362
2
votes
1
answer
104
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 ...
- 251
2
votes
1
answer
923
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
1
answer
436
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 ...
- 21
1
vote
0
answers
713
views
Is there any function to calculate condition number of sparse matrix in Eigen libraray?
The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values.
However I need to know condition number of a sparese matrix due to slow computation speed using ...
- 193
1
vote
0
answers
362
views
Condition number of finite element stiffness matrix
In the FEM, there are certain applications in which the condition number $(\kappa)$ of the overall global stiffness matrix $(A)$ is computed or reduced by some preconditioner $(P)$. Are there any ...
- 111
5
votes
1
answer
198
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}$$ ...
- 53
3
votes
2
answers
62
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}{
\...
- 131
2
votes
1
answer
184
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 ...
- 961
7
votes
0
answers
167
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 ...
- 11.1k
1
vote
1
answer
202
views
Whether should we consider the condition number of the preconditioned matrix when choosing a preconditioner?
when we solve a large sparse linear system Ax=b, using preconditioned Krylov subspace methods,e.g., gmres, should we need to reduce the condition number of the coefficient matrix? In my opinion, we ...
- 961
3
votes
1
answer
281
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?
- 840
5
votes
2
answers
928
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 ...
- 241
1
vote
1
answer
80
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$ ...
- 2,145
2
votes
1
answer
99
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 ...
- 153
1
vote
1
answer
673
views
Conjugate gradient - ill-conditioning and numerical tolerance
I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method.
Is ...
1
vote
2
answers
435
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 ...
- 29
3
votes
1
answer
207
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,145
1
vote
1
answer
58
views
Condition number of two perburbation matrix regarding limit and quadtrature integration rules
I have a question regarding the condition number of two different perturbation matrices. To start with let $A$ be a spd matrix with elements defined by $a_{i,j} = \int\limits_{\Omega\subset \mathbb{R}^...
user29088
2
votes
1
answer
193
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 ...
- 281
2
votes
1
answer
476
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 ...
- 281
6
votes
1
answer
887
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 ...
- 2,145
7
votes
2
answers
1k
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 ...
- 173
7
votes
1
answer
3k
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?
...
- 173
1
vote
2
answers
1k
views
What is a relative condition number of a sum of positive values?
We want to compute the relative condition number of:
$$x_1+x_2+x_3+\cdots$$
We assume all values are positive, and we will do a limit of a large $x_1=10^{8}$, and smaller values for all the other ...
- 2,930
13
votes
2
answers
2k
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 ...
- 727
1
vote
1
answer
309
views
Large condition number with good accuracy
In computation of the solution I achieve a solution with nice precision and small number of nodes but the condition number of the matrix is very large. I am confused. Is it possible to have a large ...
- 11
1
vote
1
answer
110
views
Numerical method for solving a system with positive definite blocks
I have a system with below coefficient matrix
$$ C = \begin{pmatrix} A & B^T \\ B & D \end{pmatrix},$$
where, $A$ and $D$ are square and positive definite. Furthermore, if $B$ be square, ...
- 13
2
votes
1
answer
370
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 \...
- 572
2
votes
1
answer
618
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 ...
- 263
2
votes
1
answer
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 ...
- 21
3
votes
1
answer
185
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^...
- 572
2
votes
0
answers
66
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,119
15
votes
1
answer
1k
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 ...
- 791
1
vote
1
answer
506
views
Direct or iterative solver for ill-conditioned problems
I have to solve an ill-conditioned sparse matrix. Once I read that iterative solvers are the better tool for such problems. Is that true? If yes, why?
- 11
3
votes
1
answer
494
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 ...
- 65
5
votes
2
answers
1k
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 ...
- 317
3
votes
2
answers
255
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 ...
- 1,463
3
votes
1
answer
619
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 $...
- 395
15
votes
2
answers
573
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, ...
- 3,143
10
votes
4
answers
568
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 ...
- 191
3
votes
2
answers
72
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-...
- 435
16
votes
3
answers
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 ...
- 5,389