|Anonymous | Login | Signup for a new account||2017-11-23 06:20 MSK|
|Main | My View | View Issues | Change Log | Roadmap | Docs|
|Viewing Issue Simple Details|
|ID||Category||Severity||Reproducibility||Date Submitted||Last Update|
|0000599||[ALGLIB] Optimization||feature||have not tried||2014-02-24 22:06||2014-06-02 17:37|
|Summary||0000599: sactivesets.sasrebuildbasis could be optimized for sparse constraint matrices|
We are using the Alglib QP solver and were experiencing some performance issues. I profiled the application and it turns out most time was spent in the code that reorthogonalizes the constraint matrices. The documentation already points out the algorithm does not scale well in the number of constraints.
For our particular QP, the constraint matrices are very sparse. I managed to get significant performance improvements by rewriting sasrebuildbasis to exploit this fact. I implemented a vector that:
- Inserts elements in O(1)
- Removes elements in O(1)
- Computes the dot product in O(nr-non-zeros)
This data structure does use more memory than normal matrices to achieve these characteristics.
If you are interested in implementing the above functionality and would like to have a reference implementation in C#, please contact me via email.
|I am wondering, did my feature request give rise to 0000607? I think you are right that we ought to be using BLEIC-QP instead of Cholesky-QP. As soon as I have time I will experiment with it. But I was under the impression both solvers needed to run sasrebuildbasis, am I right?|
|2014-02-24 22:06||nlagerr||New Issue|
|2014-02-24 22:06||nlagerr||Programming language||=> C#|
|2014-06-02 17:37||nlagerr||Note Added: 0000067|
|Mantis 1.1.6[^] Copyright © 2000 - 2008 Mantis Group|