AngouriMath
MaxEliminationWork
Field
Summary
The budget on the elimination itself, in units of one coefficient-pair
multiplication: each step adds the product of the term counts of the two operands
of each of its two products, which is what a sparse multiplication costs.
multiplication: each step adds the product of the term counts of the two operands
of each of its two products, which is what a sparse multiplication costs.
Remarks
and terms per entry. Over the whole range the unit predicts both resources
linearly and tightly: 1.4KB of allocation and 0.4µs per unit. So this budget
is about a second, and about three gigabytes of garbage, and moving it moves both
together.
finding. The cost is mild in size and violent in terms per entry — between the
fifth and the eighth power of it over the range — so no product of the two is the
right law. Worse, the most expensive input is not the widest: entries wide
enough trip MaxTerms early and the elimination
declines cheaply, while three-term entries grow just slowly enough to spend 6
seconds and 21GB before declining at size 24. The shape that costs the most is the
one just inside the term ceiling, and no bound read off the degrees can see it.
entries at size 40, which answers in 2.9 seconds having allocated 8.4GB — and to
refuse the expensive refusals, which is where it earns its keep.
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online