Institute for Reliable Computing
Head: Prof. Dr. Siegfried M. Rump

INTLAB includes a linear system solver to treat extremely ill-conditioned linear systems. It is based on a method I designed in about 1984 and uses error-free transformations for extra-precise residual calculations. Usually the method works until condition numbers of about 1030, occasionally for much larger condition numbers. The following test uses Matlab's invhilb and the right hand side ones(n,1), where the displayed condition number is the true 2-norm condition number.

Ill-coonditioned linear systems, time [sec]

    true     linear system      maximum
  dimension     cond. number     verified [sec]      rel.error
  10       1.6e+013       0.13        2.0e-015
  20       5.5e+027       0.22        5.0e-013
  30       4.3e+042       0.40        1.1e-011
  40       3.2e+057       0.7        1.7e-008
  50       4.3e+072       1.1          2.8e-009
100         2.9e+148        4.5          4.4e-002

If you are interested in extremely ill-conditioned examples, consider

A = [   -5046135670319638,    -3871391041510136, -5206336348183639,   -6745986988231149  ;
       -640032173419322,     8694411469684959,   -564323984386760,   -2807912511823001  ;
   -16935782447203334,  -18752427538303772, -8188807358110413, -14820968618548534  ;
     -1069537498856711,  -14079150289610606,  7074216604373039,    7257960283978710 ];

For details, see randmat.m. With a condition number of about 1065, this is too much for the algorithm implemented in INTLAB.

Prof. Dr. Siegfried M. Rump
Institute for Reliable Computing
Hamburg University of Technology
Am Schwarzenberg-Campus 3
21071 Hamburg
Germany