[patch] Improve automatic algorithm selection in matrix::solve()
Hi, folks. Since we've recently added solve_algo::markowitz, I thought it would be a good idea to update the automatic elimination algorithm selection logic we have for matrix::solve() (currently living in matrix::echelon_form()). To this end I've constructed a benchmark that generates random-ish matrices and measures how fast matrix::solve() can solve them. The matrix generation works by starting with a known simple solution and then permuting and mixing rows and columns randomly. You can find the code for this procedure at [1]. With that code I've generated a bunch of data points and run a quick analysis on it. Overall, the fastest (on average) algorithm seems to be: For numeric matrices: If ncells > 200 && density < 0.5: Markowitz Otherwise: Gauss For symbolic matrices: If density > 0.6 && ncells <= 12: Divfree If density > 0.6 && ncells < 120: Bareiss Otherwise: Markowitz You can find the details (and some pretty charts) at [2]. The attached patch implements this recommendation. Note that matrix::determinant() also has a similar automatic algorithm selection logic, but I didn't touch it for now. [1] https://github.com/magv/ginac-matrix-solve-bench/blob/master/mx-solve-bench.... [2] https://github.com/magv/ginac-matrix-solve-bench/blob/master/analysis.ipynb
Hi Vitaly, On 14.06.2018 15:32, Vitaly Magerya wrote:
Hi, folks. Since we've recently added solve_algo::markowitz, I thought it would be a good idea to update the automatic elimination algorithm selection logic we have for matrix::solve() (currently living in matrix::echelon_form()).
To this end I've constructed a benchmark that generates random-ish matrices and measures how fast matrix::solve() can solve them. The matrix generation works by starting with a known simple solution and then permuting and mixing rows and columns randomly. You can find the code for this procedure at [1].
With that code I've generated a bunch of data points and run a quick analysis on it. Overall, the fastest (on average) algorithm seems to be:
For numeric matrices: If ncells > 200 && density < 0.5: Markowitz Otherwise: Gauss
For symbolic matrices: If density > 0.6 && ncells <= 12: Divfree If density > 0.6 && ncells < 120: Bareiss Otherwise: Markowitz
You can find the details (and some pretty charts) at [2].
The attached patch implements this recommendation.
Note that matrix::determinant() also has a similar automatic algorithm selection logic, but I didn't touch it for now.
[1] https://github.com/magv/ginac-matrix-solve-bench/blob/master/mx-solve-bench.... [2] https://github.com/magv/ginac-matrix-solve-bench/blob/master/analysis.ipynb
Two comments on your patch. 1) This line + for (auto && r : m) { looks unconventional due to it's using rvalue refs. Is this intentional? It doesn't make a difference in GCC (same asm code). 2) Be careful when computing the matrix' density by counting non-zero elements: That loop breaks out on the first non-numeric element. The later decision on what yo use with density might be wrong. Maybe you want to compute numeric_flag and density in two separate loops? All my best, -richard.
On 06/17/2018 11:57 PM, Richard B. Kreckel wrote:
Two comments on your patch.
1) This line + for (auto && r : m) { looks unconventional due to it's using rvalue refs. Is this intentional? It doesn't make a difference in GCC (same asm code).
What I actually meant to write is "const auto &"; "auto &&" should be the same, but shorter. I think the "&&" form was introduced so that templates could seamlessly support both const and non- const usage, but I found it useful in normal code too. In any case, I'll make the "const" explicit (not that it matters in this particular example).
2) Be careful when computing the matrix' density by counting non-zero elements: That loop breaks out on the first non-numeric element. The later decision on what yo use with density might be wrong. Maybe you want to compute numeric_flag and density in two separate loops?
Dammit. My mistake, sorry. Here's the updated patch. I've additionally included a minor update to the comment near solve_algo::markowitz definition.
participants (2)
-
Richard B. Kreckel
-
Vitaly Magerya