[CoinUtils-tickets] [COIN-OR Common Utilities] #70: bug in CoinFactorization::pivot

[COIN-OR Common Utilities]

#70: bug in CoinFactorization::pivot
-------------------+--------------------------------------------------------
Reporter:  mlubin  |       Type:  defect
  Status:  new     |   Priority:  minor 
 Version:          |   Keywords:        
-------------------+--------------------------------------------------------
 I'm reposting this from the mailing list as this seems to be the more
 appropriate place.

 I believe I've found a small bug in the CoinFactorization::pivot
 routine (in CoinFactorization.hpp). The bug has the potential to cause
 memory corruption or just give the wrong answer under a very specific
 set of circumstances that wouldn't normally occur but did happen in my
 case.

 I can't claim to completely understand the code, but here's my account
 of the error (line numbers refer to the code in trunk):
 The variable "positionLargest" (CoinFactorization.hpp:900) stores the
 index of the largest element remaining in column "iColumn" after
 removing the rows that are pivoted on. A value of -1 indicates that
 there is no largest element; that is, there are no more elements in
 iColumn. Hence, at line 1041, the largest element is copied to the
 beginning of the column only if (positionLargest >= 0). In the block
 starting at line 980, extra space is allocated if needed to allow for
 all potential fill-in due to the pivot, and "positionLargest" is
 updated according to the new location of the column; however, at this
 point positionLargest could be -1. If this is the case, then
 positionLargest could satisfy the condition at line 1041 (and cause
 elements to be swapped) but actually refer to a bad memory location.
 My fix (in the attached small patch) only performs this update if
 (positionLargest >= 0).

 I believe that this causes an issue when all of these conditions are true:
 - All non-zero, non-fixed elements in a column are going to be updated in
 this pivot (and so positionLargest == -1 at line 980).
 - The column does not have space for the predicted fill in, hence the
 condition at line 980 is true and the column is moved to an area with more
 space.
 - All of the predicted fill-in is actually below the zero tolerance, so
 the column will have no nonzero, nonfixed elements (and so no largest
 element).

 I believe these conditions imply the matrix is singular, which
 explains why this bug wouldn't normally show up. Still, this bug could
 cause an issue with singularity detection (and I am working on a
 particular application where not all columns are pivoted on).

-- 
Ticket URL: <https://projects.coin-or.org/CoinUtils/ticket/70>
COIN-OR Common Utilities <http://projects.coin-or.org/CoinUtils>
Common data structures and linear algebra functions for COIN-OR projects