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.