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

[COIN-OR Common Utilities]

#71: 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 small patch below) 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).


 {{{
 --- CoinFactorization.hpp       2011-12-10 22:10:11.422567093 -0600
 +++ CoinFactorization.hpp.patched       2011-12-10 22:13:27.935310876
 -0600
 @@ -983,7 +983,7 @@
         return false;
        }
        //redo starts
 -      positionLargest = positionLargest + startColumnU[iColumn] -
 startColumn;
 +      if (positionLargest >= 0) positionLargest = positionLargest +
 startColumnU[iColumn] - startColumn;
        startColumn = startColumnU[iColumn];
        put = startColumn + numberInColumn[iColumn];
      }

 }}}

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