commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (JIRA)" <>
Subject [jira] [Commented] (MATH-1079) Performance improvements for the SimplexSolver
Date Wed, 18 Dec 2013 17:47:09 GMT


Thomas Neidhart commented on MATH-1079:

After some thoughts there were still some substantial improvements possible:

 * do not perform subtractRow if the multiplier is exactly 0, as in this nothing will change
 * move cutOff detection from row operations to pivot selection process
 * change default cutOff threshold from 1e-12 to 1e-10

With these changes, execution speed further increased, test case grow15 from netlib:

 * before changes: ~10s
 * after first batch of changes: ~5s
 * now: ~1.5s

Need to add performance tests based on the samples from netlib.
Is it possible to add the example files from netlib to subversion considering licensing issues?

> Performance improvements for the SimplexSolver
> ----------------------------------------------
>                 Key: MATH-1079
>                 URL:
>             Project: Commons Math
>          Issue Type: Improvement
>            Reporter: Thomas Neidhart
>             Fix For: 3.3
> Tests with various larger models in mps format from have shown that there
is a lot of room for improvements for the SimplexSolver.
> Currently, the tableau is stored in a RealMatrix, and each access to an entry uses the
getEntry / setEntry methods which always does bounds checking. This is inefficient and unnecessary
as we know that we access the matrix within bounds.
> Suggest to access the internal array directly for various operations. The walkInXXX method
of RealMatrix can not always be used for this purpose.
> Also the getBasicRow() method can be a bottle-neck as it always needs to analyze the
whole tableau to determine the row in which a variable is basic. It would be better to keep
track of which variables are basic in which row.

This message was sent by Atlassian JIRA

View raw message