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
4 votes
1 answer
100 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 ...
user avatar
  • 149
4 votes
1 answer
213 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 ...
user avatar
2 votes
0 answers
96 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 ...
user avatar
2 votes
1 answer
91 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 ...
user avatar
  • 251
2 votes
1 answer
343 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 ...
user avatar
2 votes
1 answer
255 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 ...
user avatar
  • 21
1 vote
0 answers
367 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 ...
user avatar
1 vote
0 answers
122 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 ...
user avatar
  • 111
5 votes
1 answer
147 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}$$ ...
user avatar
  • 53
3 votes
2 answers
59 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}{ \...
user avatar
  • 131
2 votes
1 answer
149 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 ...
user avatar
  • 951
7 votes
0 answers
132 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 ...
user avatar
1 vote
1 answer
144 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 ...
user avatar
  • 951
3 votes
1 answer
221 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?
user avatar
5 votes
1 answer
486 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 ...
user avatar
  • 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$ ...
user avatar
  • 2,001
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 ...
user avatar
  • 121
1 vote
1 answer
385 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 ...
user avatar
1 vote
2 answers
343 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 ...
user avatar
  • 29
2 votes
1 answer
172 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}^{\...
user avatar
  • 2,001
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
153 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 ...
user avatar
2 votes
1 answer
301 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 ...
user avatar
6 votes
1 answer
618 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 ...
user avatar
  • 2,001
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 ...
user avatar
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? ...
user avatar
1 vote
2 answers
938 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 ...
user avatar
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 ...
user avatar
1 vote
1 answer
244 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 ...
user avatar
  • 11
1 vote
1 answer
108 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, ...
user avatar
  • 13
2 votes
1 answer
237 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 \...
user avatar
  • 562
2 votes
1 answer
566 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 ...
user avatar
  • 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 ...
user avatar
  • 21
3 votes
1 answer
149 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^...
user avatar
  • 562
2 votes
0 answers
54 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 ...
user avatar
  • 1,109
14 votes
1 answer
997 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 ...
user avatar
  • 771
1 vote
1 answer
409 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?
user avatar
  • 11
3 votes
1 answer
386 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 ...
user avatar
5 votes
2 answers
965 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 ...
user avatar
  • 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 ...
user avatar
  • 1,443
3 votes
1 answer
543 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 $...
user avatar
15 votes
2 answers
513 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, ...
user avatar
  • 3,003
10 votes
4 answers
521 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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 5,259
7 votes
1 answer
637 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 ...
user avatar
  • 2,001
8 votes
1 answer
131 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 ...
user avatar
  • 3,450
3 votes
1 answer
309 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 ...
user avatar
9 votes
3 answers
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 ...
user avatar
  • 167
9 votes
1 answer
8k 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 ...
user avatar
  • 235