In our previous article we described a packed representation for sparse polynomials is designed for scalability and high performance. The expand and divide commands in Maple 14 use this representation internally to multiply and divide polynomials with integer coefficients, converting to and from Maple's generic data structure described here. In this post I want to show you how these algorithms work and why they are fast. It's a critical stepping stone for our next topic, which is parallelization.

Our first article introduced Maple's polynomial data structure and explained how Maple spends a lot of time working with monomials. To multiply polynomials having n and m terms, Maple must construct, simplify, hash, and sort all nm pairwise products to determine what monomials are equal. This work is performed even if the result has far fewer than nm terms, making it a rather inefficient way to multiply large multivariate polynomials. This article describes a new data structure for multivariate polynomials that is being added to Maple for a future release.

9xy³z  -  4y³z²  -  6xy²z  -  8x³  -  5

This is the first in a series of short informal articles about our efforts to speed up polynomial arithmetic in Maple. We begin with an example of how polynomials are represented in Maple right now.

9xy³z  -  4y³z²  -  6xy²z  -  8x³  -  5

When you enter a polynomial in Maple, it creates a generic data structure like the one above. In Maple's representation this polynomial is a sum of terms that is 11 words of memory long where each word is either 32 or 64 bits. For each term it stores a pointer to a monomial followed by a coefficient.

If you're writing an external library to be called from Maple, then you have the following problem. The user wants to interrupt your code. They are valiantly pressing control-C or the stop button in the Maple GUI, as your code grinds their machine to a halt. What do you do ?

Suppose you want to solve a large dense linear system AX=B over the rationals - what should you do? Well, one thing you should probably not do is directly apply Gaussian elimination. It does O(n^3) arithmetic operations, but the size of the numbers blow up, leading to an exponential bit complexity. Don't believe me? Try it:

I am pleased (and terrified) to announce the first public release of a Maple library for high performance sparse polynomial arithmetic. This C library and Maple interface is under development at Simon Fraser University in Vancouver, Canada. We are releasing this interim version so that Maple enthusiasts and researchers can try it. Maple 11 is required.

When working with large sparse linear systems you often want to look at their non-zero structure, however Maple's existing tools are all designed for dense matrices. I wrote a little tool to produce images like this in reasonable time. You can download the code here, and the rest of this post is a quick tutorial on how to use the included command. Maple 11 is required.

What is the largest linear system that Maple can solve? You might be surprised to find out. In this article we present strategies for solving sparse linear systems over the rationals. An example implementation is provided, but first we present a bit of background.

Sparse linear systems arise naturally from problems in mathematics, science, and engineering. Typically many quantities are related, but because of an underlying structure only a small subset of the elements appear in most equations. Consider networks, finite element models, structural analysis problems, and linear programming problems.

Maple 11 has been out for a while now so hopefully people have it. I thought I would write a short post detailing some of what was done in the area of Groebner bases. If you run the examples in Maple 10 and Maple 11, I would appreciate it if you could post the times and the specifications of your computer.

This is a quick programming exercise to correct the following problem in Maple:

for n from 8 to 12 do 
  A := Matrix(2^n, 2^n, storage='sparse'):  # zero matrix
  print( 2^n, time(LinearAlgebra:-Transpose(A)) );
end do:

The problem is that the LinearAlgebra:-Transpose command is not sparse. That is, the time it takes is proportional to the overall size of the matrix and not to the number of non-zero entries - even when your matrix uses sparse storage. In this post we will look at what is required to program a new Transpose command which can handle much larger matrices.