Efficiently initializing polynomials

[Nils Bruin]

The following question is motivated by https://trac.sagemath.org/ticket/28512 .

The code currently in sage to interface with libsingular creates by default polynomials by repeatedly adding monomials together. It currently does that by adding terms one-by-one, each time copying over the result and deleting the previous result. That leads to very noticeable quadratic time. The could be alleviated by adding the term in a balanced way, so that there are only very few manipulations of polynomials with very many terms.

However, even that is a little silly: in this cases we are adding together monomials that we already know are distinct, so addition should just be a merge-sort operation on the terms. We know the monomials will not cance and generally, we already know the total number of terms. Is there a way of handing a collection of terms to libsingular and constructs the polynomial that is the sum of those terms? Or some other way to quickly construct a polynomial with known terms.

Kind regards,

Nils

[han...@mathematik.uni-kl.de]

The solution to increase the speed in the addition of many terms are
"geo buckets", implemented in the type sBucket in Singular.
Instead of having +: poly, poly -> poly and =:poly -> poly
we have +:poly,poly->sBucket, +:sBucket,poly->sBucket and
=:sBucket->poly.
For the implementation and procedures to use see (in Singular/iparith.cc):
jjPLUS_B (+:poly,poly->sBucket)
jjPLUS_B_P (+:sBucket,poly->sBucket)
and in Singular/ipassign.cc:
jiA_BUCKET (=:sBucket->poly)

Hans Schoenemann

[Nils Bruin]

On Friday, September 27, 2019 at 7:01:53 AM UTC-7, han...@mathematik.uni-kl.de wrote:

The solution to increase the speed in the addition of many terms are
"geo buckets", implemented in the type sBucket in Singular.
Instead of having +: poly, poly -> poly and =:poly -> poly
we have +:poly,poly->sBucket, +:sBucket,poly->sBucket and
=:sBucket->poly.
For the implementation and procedures to use see (in Singular/iparith.cc):
jjPLUS_B (+:poly,poly->sBucket)
jjPLUS_B_P (+:sBucket,poly->sBucket)
and in Singular/ipassign.cc:
jiA_BUCKET (=:sBucket->poly)

Thanks! that's exactly the kind of pointer I was looking for.

 

Hans Schoenemann

[Nils Bruin]

On Friday, September 27, 2019 at 7:01:53 AM UTC-7, han...@mathematik.uni-kl.de wrote:

The solution to increase the speed in the addition of many terms are
"geo buckets", implemented in the type sBucket in Singular.
Instead of having +: poly, poly -> poly and =:poly -> poly
we have +:poly,poly->sBucket, +:sBucket,poly->sBucket and
=:sBucket->poly.
For the implementation and procedures to use see (in Singular/iparith.cc):
jjPLUS_B (+:poly,poly->sBucket)
jjPLUS_B_P (+:sBucket,poly->sBucket)
and in Singular/ipassign.cc:
jiA_BUCKET (=:sBucket->poly)

Thank you!

Looking at the include files for libsingular (the ones in local/include/singular; so probably the definitions meant to be exported) do not include these particular routines, but there are bindings available in singular/sbuckets.h for things like:

sBucketCreate(ring r);

sBucket_Merge_p(sBucket_pt bucket, poly p, int lp);

sBucket_Add_p(sBucket_pt bucket, poly p, int lp);

sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)

which seem to provide exactly the kind of interface you are describing. Is there a reason you prefer the routines you mention over these? Is it just a matter of c vs. c++ (the content of sbuckets.h seems like valid c to me, so I'm assuming it provides a "c" interface)

[han...@mathematik.uni-kl.de]

On Fri, Sep 27, 2019 at 09:00:52AM -0700, Nils Bruin wrote:
> Looking at the include files for libsingular (the ones in
> local/include/singular; so probably the definitions meant to be exported)
> do not include these particular routines, but there are bindings available
> in singular/sbuckets.h for things like:
>
> sBucketCreate(ring r);
> sBucket_Merge_p(sBucket_pt bucket, poly p, int lp);
> sBucket_Add_p(sBucket_pt bucket, poly p, int lp);
> sBucketDestroyAdd(sBucket_pt bucket, poly *p, int *length)
>
> which seem to provide exactly the kind of interface you are describing. Is
> there a reason you prefer the routines you mention over these? Is it just a
> matter of c vs. c++ (the content of sbuckets.h seems like valid c to me, so
> I'm assuming it provides a "c" interface)
>

The definitions should be the same (only that libsingular.h does not
include everything). But sbucket.c is a c++ file.

Hans Schoenemann

[Nils Bruin]

On Monday, September 30, 2019 at 1:05:18 AM UTC-7, han...@mathematik.uni-kl.de wrote:

The definitions should be the same (only that libsingular.h does not
include everything). But sbucket.c is a c++ file.

Thank you! This made a big difference. Indeed, I see now that sBucket itself is already a c++ class. Cython is happy to work with that, though, so there are no interface problems.