PolynomialBB

[B.David Saunders]

Clement, What does PolynomialBB expect for the polynomial template parameter?
I tried to use a vector or deque with PolynomialBB in my response to Tibouchi's
request on linbox-use, but found the polynomial type is supposed to have rebind.

Jean-Guillaume, When I tried deque, massey-domain had a problem for lack of a
reserve function. Is that reserve() really necessary? It is a shame that a
deque can't be the container there (I want to pop from the front).

Attached are the code and compiler error msgs.

-dave

[Jean-Guillaume Dumas]

B.David Saunders wrote:
> Jean-Guillaume, When I tried deque, massey-domain had a problem for lack of a
> reserve function. Is that reserve() really necessary?

Well the idea is that the polynomial will grow all along the algorithm,
but that we know
its size is bounded by n+1, therefore it is a loss of efficiency to use
any dynamical memory allocation even amorticized.
reserve/resize makes thus things go faster.

> It is a shame that a
> deque can't be the container there (I want to pop from the front).
>

OK, but it still want to keep the efficiency.

Then I see several alternatives :
1/ let the user reserve himself the memory at n+1 before the call
2/ use a hack : to do C=Polynomial(n+1) instead of C.reserve(n+1),
before the resize to 1, might do the job when possible and nothing
really bad otherwise ...
3/ another way for you is to convert the polynomial type before and
after the call to massey
4/ make two different massey routines : an inplace and a notinplace ...

if there are not so many calls to massey, then 3 is working right now
without changing anything
otherwise we should investigate solution 2 ?
Best,

--

Jean-Guillaume Dumas.
____________________________________________________________________
Jean-Guill...@imag.fr Tél.: +33 476 514 866
Université Joseph Fourier, Grenoble I. Fax.: +33 476 631 263
Laboratoire Jean Kuntzmann, Mathématiques Appliquées et Informatique
51, avenue des Mathématiques. LJK/IMAG - BP53. 38041 Grenoble FRANCE
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas
____________________________________________________________________

[B.David Saunders]

Jean-Guillaume Dumas wrote:
> B.David Saunders wrote:
>> Jean-Guillaume, When I tried deque, massey-domain had a problem for lack of a
>> reserve function. Is that reserve() really necessary?
> Well the idea is that the polynomial will grow all along the algorithm,
> but that we know
> its size is bounded by n+1, therefore it is a loss of efficiency to use
> any dynamical memory allocation even amorticized.
> reserve/resize makes thus things go faster.
>> It is a shame that a
>> deque can't be the container there (I want to pop from the front).
>>
> OK, but it still want to keep the efficiency.
>
> Then I see several alternatives :
> 1/ let the user reserve himself the memory at n+1 before the call
> 2/ use a hack : to do C=Polynomial(n+1) instead of C.reserve(n+1),
> before the resize to 1, might do the job when possible and nothing
> really bad otherwise ...
> 3/ another way for you is to convert the polynomial type before and
> after the call to massey
> 4/ make two different massey routines : an inplace and a notinplace ...
>
> if there are not so many calls to massey, then 3 is working right now
> without changing anything
> otherwise we should investigate solution 2 ?
> Best,
>

I agree that massey can be left as is, because
on second thought, I don't need the deque. My goal is to divide the minpoly by
x in constant time. I should be able to do that by making a subvector on the
minpoly (a vector). f = Subvector(m.begin()+1, m.end()) is rep of m(x)/x.
(I'm not checking/using exact syntax right now).

Now I want to build a PolynomialBB from f. That seems to require a bug fix.

-dave

btw, I'm thinking about some design ideas.
Goals: 1. Get to Clement's desire mentioned on the wiki to have dense matrix
and blackbox as just two classes. ...thus facilitate coding and separate
compilation.
2. make block methods easier to implement (also packed representations over tiny
primes).

Plan (roughly): BB base class has as template parameters the field(ring) type
and the dense submatrix type. Apply() is not a template, is defined on the
dense submatrix type (rather than vectors) which in turn is defined only in
terms of pointers to Element and strides. Thus we can have again a virtual base
class for BB. Defining some casts to the dense submatrix type can allow
implicit conversions to make life easier for users of apply. I believe that the
key operations of apply and hom can work in this setup. More on this after the
ISSAC deadline...