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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
210 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
749 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
102 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
227 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
98 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
93 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
513 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
298 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
427 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 ...
1 vote
0 answers
148 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
160 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
61 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
164 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 ...
  • 971
7 votes
0 answers
141 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 ...
1 vote
1 answer
153 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 ...
  • 971
3 votes
1 answer
238 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?
5 votes
1 answer
579 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,031
2 votes
1 answer
94 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 ...
  • 121
1 vote
1 answer
424 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
369 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
181 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,031
1 vote
1 answer
56 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}^...
user avatar
2 votes
1 answer
165 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
1 answer
342 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 ...
6 votes
1 answer
678 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,031
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 ...
7 votes
1 answer
1k 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? ...
1 vote
2 answers
989 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 ...
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 ...
1 vote
1 answer
260 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
109 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
271 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 \...
  • 562
2 votes
1 answer
580 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
157 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^...
  • 562
2 votes
0 answers
62 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
14 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 ...
  • 771
1 vote
1 answer
443 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
399 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 ...
5 votes
2 answers
995 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
232 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,443
3 votes
1 answer
565 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 $...
15 votes
2 answers
523 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,023
10 votes
4 answers
532 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
71 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,299
7 votes
1 answer
661 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,031
8 votes
1 answer
138 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,540
3 votes
1 answer
313 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 ...