Mr. Roman Pearce

## 1683 Reputation

19 years, 297 days
CECM/SFU
Research Associate

I am a research associate at Simon Fraser University and a member of the Computer Algebra Group at the CECM.

## Just try installing it and...

Just try installing it and do the activation, etc. If that doesn't work Call Maplesoft tech support. It should be possible.

## use [] to make lists...

Square brackets are the simplest and fastest way.  Internally Maple represents a lists as an object with a pointer to an expseq, so there is not any copying or overhead involved.

## while loop and next...

Make it a while loop and explicitly update the loop counter at the end of the loop. Then use the next keyword to restart the loop.

## Groebner bases...

Now you have two extensions so the computation takes place over the product of GF(2^3) and GF(2^2). alpha*beta is a field element, right? Also, for your other question. Maple does not use any special representation for finite fields. There is fast C code (FGb) for Zp, where p is a half-word prime, but other than that it is done by adding the field relations to the set of polynomials. Aside from FGb, which is used for graded reverse lexicographical order, Maple's algorithms aren't particularly fast. Maple's data structures and interpreted code are bottlenecks, but the actual algorithms are fairly good. Maple uses F4, FGLM, and the Groebner walk. These are optimized for sparsity, so for a lot of "geometric" problems you are likely to get an answer. They will get bogged down doing dense elimination or when coefficients blow up though. As for Magma and Sage, Sage uses the Singular computer algebra system to compute Groebner bases. Singular is not as fast as Magma in the finite field case or over the rationals, but it is fairly quick. Singular has an advantage over rational function fields in that it uses the slimgb algorithm.

## indets...

use the indets command, indets(L); see the help page ?indets

## immutable...

Lists and polynomials are immutable in Maple (changing them makes an entirely new object) so you can just use = to test. For example: ``` A := [x^2+x+1,x-1]; B := [x^2+x+1,x-1]; evalb(A=B); ```

## choose polynomials containing given vari...

select(f->indets(f)={a,b,c}, L);

## wrong file...

I think this is the wrong file, or somehow the system is missing. Can you just post the generators in Maple notation? If you made an ideal, copy the output of lprint(Generators(J)):

## floats in Groebner...

Wow, that one little float created quite a mess for Groebner and PolynomialIdeals. We should probably check for floats and return an error. None of the algorithms in either package are designed to handle floats.

## F3 - break execution group...

Open it up and start hitting F3. It will split the big execution group into two. You might try splitting it in half a few times, then saving the file under a different name.

## handwriting pi...

I can *never* get it to recognize pi with either a tablet or mouse.

## F4...

It's rather difficult to implement F4 in Maple and have it run fast. The problem is that Maple lacks an appropriate data structure for sparse linear algebra. This is how I would do it in C. It helps to think of the algorithm as running over a finite field so that all the coefficients are the same size and there is no coefficient blowup.

In each iteration, F4 computes a batch of S-polynomials and reduces them. It doesn't particularly care about the remainders of these polynomials, it's just trying to find new leading monomials. So imagine you wrote down the S-polynomials and kept their terms sorted in a monomial order. Eliminate the largest monomial(s) from the polynomials in any way you want. Discard zeros. Then add these polynomials to the basis, compute all the S-polynomials, and repeat. It helps to think of these polynomials as rows in a matrix.

You'll notice that eliminating the largest monomial sounds an awful lot like polynomial division. This is not a co-incidence, polynomial division is equivalent to a linear algebra problem. In F4 you have much more flexiblility for eliminating terms because you have a set of polynomials that you're reducing, and a set of polynomials you're dividing by. So there are many different strategies you could use. Algorithms such as SlimGB exploit the sparsity of polynomials and the size of the coefficients.

It is very desirable to implement the algorithm without storing the entire matrix in memory or operating on entire rows at once. More "working storage" means slower algorithm. Ideally you should only operate on the leading elements, and construct the rest of the polynomials term by term, as you need them, on the fly. For an idea of how to do this, see Stephen C. Johnson "Sparse Polynomial Arithmetic" and note the algorithms with a heap. You may also be interested in my papers at http://www.cecm.sfu.ca/~rpearcea/

## gcd is for polynomials...

The gcd command is for a polynomial gcd. You need to use igcd for an integer gcd.

## Groebner[Basis] always reduced...

The basis returned by Groebner[Basis] is always reduced. The polynomials are normalized to eliminate fractions and common divisors from the coefficients. If the ideals are equal, they will return the same basis.