[jira] [Comment Edited] (MATH-1079) Performance improvements for the SimplexSolver

["Thomas Neidhart (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/MATH-1079?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13851957#comment-13851957 ] 

Thomas Neidhart edited comment on MATH-1079 at 12/18/13 5:46 PM:
-----------------------------------------------------------------

After some thoughts there were still some substantial improvements possible:

 * do not perform subtractRow if the multiplier is exactly 0, as in this case 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?


was (Author: tn):
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: https://issues.apache.org/jira/browse/MATH-1079
>             Project: Commons Math
>          Issue Type: Improvement
>            Reporter: Thomas Neidhart
>             Fix For: 3.3
>
>
> Tests with various larger models in mps format from netlib.org 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
(v6.1.4#6159)