June 2018 - GiNaC-list

[patch] Improve automatic algorithm selection in matrix::solve()
by Vitaly Magerya 18 Jun '18

18 Jun '18

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

2 2

[patch] Add 'algo' parameter to matrix::rank()
by Vitaly Magerya 12 Jun '18

12 Jun '18

Hi, folks. Currently matrix::rank() is hardcoded to use Bareiss elimination, which for some matrices is way too slow (and I had to work around this limitation in my own code). I propose adding an argument that will allow users to select which elimination scheme to use. The argument is the same as matrix::solve() takes (so, solve_algo::*). I've tried to mimic how a similar argument was added to matrix::inverse() by keeping the current set of rank() functions and defining separate ones with the 'algo' argument, with the old ones calling the new ones with solve_algo::automatic. This is instead of using default argument values. I've also put the code that makes the automatic selection of the elimination method into a separate function so that both matrix::solve() and matrix::rank() could share it. There's a bit of similar code in matrix::determinant(), but since the self of determinant algorithms is different from the elimination algorithms, it's not clear if these two could be unified.

2 2

Re: [GiNaC-list] [patch] Add solve_algo::markowitz for large sparse systems
by Vitaly Magerya 08 Jun '18

08 Jun '18

On 05/31/2018 05:55 PM, Richard B. Kreckel wrote: > Thanks a lot for your contribution! After doing some (probably too > simplistic) checks with your implementation of Markowitz-ordered > Gaussian elimination and finding no issues I've committed it. > > Regarding style, I've taken the liberty to adjust indentation a little > bit to comply with <https://www.cebix.net/indentation.html>. Thanks; I tried to mimic the style of the rest of the code, but it turned out to be challenging. Is there a set of vim options that implement this style? > Also, > please let's keep the continue statements in conditionals on a line of > their own. This improves debuggability. Apart from that, it's perfect. Sure.

1 0

ldegree changes after expand
by Matthias Naaf 04 Jun '18

04 Jun '18

Dear All, I've just hit an unexpected behavior of the ex.ldegree() method in my application. The problem is that ldegree() gives 0 before and 1 (the expected value) after calling expand() on the expression. I did not expect this, as the tutorial says that degree() and ldegree() "work reliably on non-expanded input polynomials". A small running example and its output are attached. The expression is the one I encountered in my application. This looks like a bug to me, or is it necessary to call expand() before using ldegree()? A related question: What about coeff(), should I call expand() before using coeff()? GiNaC version: 1.7.4 g++ version: 7.3.1 openSUSE (tumbleweed) Thanks in advance for any help on these questions Matthias

2 2