Tableau pivoting performance issue

[riccardodebenedictis]

Most of the time (>85%) of a standard resolution process is spent in performing pivoting operations. Until better strategies are found, which would minimize the need of such operations, it could be worth to optimize them.

A tableau data structure, with the following characteristics, should be introduced:

• dynamic introduction of new rows/columns (new variables should be efficiently introduced)
• efficient retrievals of the non-zero indices for a given row/column (for efficient pivoting operation)
• storing of the sole non-zero elements (the tableau is highly sparse.. not much a memory issue, rather an efficiency issue)

Notice that pivoting operations can be parallelized, further enhancing efficiency!

[riccardodebenedictis]

the pivoting procedure has been enhanced resulting in more than 50% performance improvement. parallelizing the pivoting procedure results in too much time: the thread creation does not seam to worth the parallelization..