Richard Kreckel [Mon, 3 Aug 2020 16:20:27 +0000 (18:20 +0200)]
Make workarounds for sqrfree_yun() obsolete.
Since Yun's algorithm is based on polynomial GCD, it only finds factors
up to a unit. Callers shouldn't have to work around this, so sqrfree_yun()
now does a final polynomial long division to compute the lost factor and
fixes the result before returning.
Richard Kreckel [Mon, 3 Aug 2020 16:09:30 +0000 (18:09 +0200)]
[BUGFIX] Fix factor_univariate(poly, x) for constant poly.
The modular factorization fails to find a prime in this case, leading to
an infinite loop. At least one caller (factor_sqrfree) happens to produce
such constant polys in some cases.
Richard Kreckel [Tue, 7 Apr 2020 21:56:25 +0000 (23:56 +0200)]
[PATCH] Check number of parameters when reading function from archive.
Functions where looked up by their function name in archives. However,
some functions have overloads for different numbers of parameters
('zeta', 'G', 'psi'). Reading archives could pick the wrong overload.
Fixed by requiring that the actual number of function parameters in the
archive node must equal the function's declared number of parameters.
Richard Kreckel [Sun, 22 Sep 2019 11:19:00 +0000 (13:19 +0200)]
Remove exhashmap<T> class.
Class exhashmap<T> was a workaround for missing std::hash_map<Key, T>
in the original C++98 standard. It was put in GiNaC because map<Key, T>
was deemed too slow. Since C++11 there is std::unorderd_map<Key, T>,
which is hash-based. To be able to use it, add specializations of
std::hash<ex> and std:equal_to<ex>.
Richard Kreckel [Fri, 3 May 2019 19:14:20 +0000 (21:14 +0200)]
[DOC] Change library order in tutorial example.
Some systems care about library ordering: Dependent libraries must be
linked last. Let's link with -lginac before -lcln in the example so it
will work on any system, even on Windows.
Richard Kreckel [Sat, 9 Mar 2019 17:40:32 +0000 (18:40 +0100)]
Refactor matrix::determinant_minor() a bit.
Remove special cases for small matrices and for for last column
minor computation. Add early return for the case that all minors
relevant for one column turn out to be zero. Improve some comments.
Richard Kreckel [Sat, 16 Feb 2019 11:58:38 +0000 (12:58 +0100)]
Fix elusive bug in expairseq ctor.
When an expair turns out to represent a number, that should go into
the expairseq's overall_coeff. This was accomplished by class mul,
thanks to the override of expair_needs_further_processing(), but not
always for class add.
This patch fixes the base class' expair_needs_further_processing()
with similar logic as that already in place for class mul.
Vitaly Magerya [Fri, 12 Oct 2018 18:45:27 +0000 (20:45 +0200)]
Handle un-normal zeros properly in the division-free elimination.
Call .normal() instead of just .expand(), such that matrix::pivot() finds
the pivot.
Note that this problem also affects matrix::solve() with 'algo'
set to solve_algo::automatic.
Of course, using .normal() makes division_free_elimination only
truly "division-free" if the input matrix didn't have fractions.
In other cases, GCDs will be computed.
Vitaly Magerya [Wed, 13 Jun 2018 21:07:45 +0000 (23:07 +0200)]
Add optional matrix::rank() algorighm selection.
Before, matrix::rank() was 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.
This algorithm avoids the 'fill-in' problem of Gaussian elimination
and significantly improves the times for solving large sparse systems.
See: <https://www.ginac.de/pipermail/ginac-list/2018-May/002202.html>.
Richard Kreckel [Wed, 31 Jan 2018 09:04:25 +0000 (10:04 +0100)]
Improve gcd(a, b) where one argument is a power of a symbol.
The already implemented recursion
gcd(x^n, x*p(x)) -> x*gcd(x^(n-1), p(x))
is not ambitious enough: If p(x) has a factor of x, it just goes through
the same step again, and if p(x) has a factor which is a power of x, this
is reapeted many times.
Example:
gcd(x^n, expand(x^n*(1+x)))
used to go recurse through the gcd routine n times, which could
easily lead to a stack overflow for n about 10^5.
To improve the situation, introduce a special case for gcd where one
argument is a power of a symbol and just cancel the common factor.
This turned out to be the root cause of segfaults in matrix elimination
algorithms, as reported by Patrick Schulz and Vitaly Magerya:
Cf. <https://www.ginac.de/pipermail/ginac-list/2018-January/thread.html>
Richard Kreckel [Sun, 28 Jan 2018 18:59:54 +0000 (19:59 +0100)]
[CHECK] Add some more factorization exams.
Add the 15 multivariate polynomials from P. S. Wang's paper "An
Improved Multivariate Polynomial Factoring Algorithm" as exams.
Don't add them as benchmarks since timings vary considerably
depending on internal choice of variables. In any case, this should
never take hours. (But before 630db9a0b0 it did, occasionally.)
Richard Kreckel [Sun, 28 Jan 2018 18:23:50 +0000 (19:23 +0100)]
Add optional algorithm selection to matrix::inverse().
Following a proposal by Vitaly Magerya, a signature with a solve_algo
is added to class matrix. (Not using a default argument in order to
not break the ABI.)
Richard Kreckel [Wed, 24 Jan 2018 21:37:24 +0000 (22:37 +0100)]
Speed up special cases of square-free factorization.
Square-free factorization of polynomials containing a factor which is
a high power P of a symbol x did scale like O(P) in space and time.
This patch introduces a shortcut in Yun's algorithm, such that the
computation is only O(1) in space and time.
This makes it possible to compute, say sqrfree(x^P + x^(P+1)) =>
(1+x)*x^P with P=123456789.
Found this to be a bottleneck while debugging one of Vitaly Magerya's
examples.
Richard Kreckel [Wed, 15 Feb 2017 11:58:48 +0000 (12:58 +0100)]
Clean up combinatorial helpers.
* Convert all signatures from int to unsiged.
* Renamed partition_generator to partition_with_zero_parts_generator...
* ...and add class partition_generator which does not include zero parts.
* Rename ::current() to ::get() and make them compute vectors on first use.
git://www.ginac.de / ginac.git / log