search

ERGO-Code / HiGHS

Linear optimization software
MIT License
957 stars 177 forks source link

How good is the HiGHS condition estimate? #1944

Open jajhall opened 3 weeks ago

jajhall commented 3 weeks ago

HiGHS uses the basis condition estimate in Hager84 . All that's required is five solves with each of B and B^T for a full RHS

The value is extracted using Highs::getKappa (see #1869)

Hager only tests on random matrices.

How accurate is it?

kbrix2000 commented 2 weeks ago

The method by Hager84 (DOI: 10.1137/0905023) estimates the condition number with respect to the l_1 norm. Out of curiosity: Is that what we need?

HighamTisseur2000 (DOI: 10.1137/S0895479899356080, eprint) propose a modification of Hager's algorithm, which is also implemented in LAPACK. Furthermore, the authors also refer to other estimators including that by Cline, Moler, Stewart, and Wilkinson available in LINPACK. @jajhall Concerning the accuracy on page 1185 Higham and Tisseur write "The LINPACK and LAPACK estimators both produce estimates that in practice are almost always within a factor 10 and 3, respectively, of the quantities they are estimating.". They provide references for these results, which might also be of interest, and there are also further discussions on the accuracy in the paper.

jajhall commented 2 weeks ago

The 1-norm (or \infty-norm) is all that's required

Thanks for the other references. I'll stick with the Hager estimate for now, particularly if more extensive experiments show it to be accurate enough. However, as a NLA fan, I'll be sure to look at the others sometime!

kbrix2000 commented 2 weeks ago

Ok, just let me know if I can help.