[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] GLPK failure to invert matrix
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] GLPK failure to invert matrix |
Date: |
Thu, 17 May 2007 15:23:58 +0400 |
> I have a problem that has few integer parameters defining the size
> of the problem. It's like the large non-square underdefined linear
> equation AX=F with extra >= conditions.
> When I downscale parameters such that problem becomes just the
> square linear equation GLPK fails with error beginning with size
> ~700:
> 0: objval = 1.427134885e-02 infeas = 1.000000000e+00 (0)
> 200: objval = 3.448379584e-03 infeas = 3.724860891e-01 (0)
> 203: objval = -7.866243389e-19 infeas = 1.314442221e-16 (500)
> * 203: objval = -7.866243389e-19 infeas = 8.259452150e-16 (500)
> * 400: objval = 0.000000000e+00 infeas = 0.000000000e+00 (303)
> spx_invert: the basis matrix is ill-conditioned
> spx_simplex: numerical problems with basis matrix
> spx_simplex: sorry, basis recovery procedure not implemented yet
> lpx_simplex: cannot recover undefined or non-optimal solution
> Time used: 26.0 secs
> Memory used: 104.3M
This a lack of the glpk simplex solver. I hope to implement a new
version of the solver, which includes the basis recovery procedure.
> This suggests that GLPK failed to compute LU-factorization of the A
> matrix. At the same time LAPACK package is able to find
> LU-factorization and invert the same matrix quite easily with their
> 'dgetrf' and 'dgetri' functions called in sequence.
> Is it reasonable to expect GLPK to invert this kind of matrices?
> Would this be a valid enhancement request?
Ill-conditioned matrix means that its condition number is too large
(in this case is larger than 1e12), so the solution cannot be obtained
with a sufficient accuracy. AFAIK, dgetrf checks only for exact
singularity, besides it uses partial pivoting. Could you estimate the
condition number of your matrix?
> I can provide this problem's description if necessary.
Please do that.
Andrew Makhorin