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.
63
questions
3
votes
1
answer
222
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
793
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
105
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
263
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
101
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
1
answer
96
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
697
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
353
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
552
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
238
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
177
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
172
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
153
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 ...
- 10k
1
vote
1
answer
178
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
255
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?
- 830
5
votes
1
answer
709
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
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$ ...
- 2,055
2
votes
1
answer
97
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
528
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
410
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
2
votes
1
answer
189
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,055
1
vote
1
answer
57
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
180
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
432
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
778
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,055
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
2k
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,900
13
votes
2
answers
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 ...
- 697
1
vote
1
answer
284
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
331
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
600
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
172
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
63
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,109
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 ...
- 781
1
vote
1
answer
471
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
428
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
239
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,453
3
votes
1
answer
590
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 $...
- 385
15
votes
2
answers
555
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,043
10
votes
4
answers
546
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,359
7
votes
1
answer
699
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 ...
- 2,055
8
votes
1
answer
141
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 ...
- 3,570
3
votes
1
answer
326
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 ...
- 143