roman_pearce

A lot of people want to do very large computations which require a lot of RAM.  But above a certain threshold, the cost of memory explodes.  We had this idea but no excuse to try it.  Buy a good SSD and use it for a swap partition.  I suggest the Intel X25-M.  Make sure you have at least 1/10th of its size in RAM, i.e. 8GB of RAM for an 80GB drive, but of course more is better.  The RAM should act as a massive cache for the SSD, giving you another...

Is it possible to import the branch structure of discussions from the old MaplePrimes?  In many cases it looks like all the replies are put into a flat list.

Our previous article described the design of fast algorithms for multiplying and dividing sparse polynomials. We have integrated these algorithms into the expand and divide commands of Maple 14. In this post I want to talk a bit about what you might see when you try Maple 14. Keep in mind that the product isn't released yet and I don't work for Maplesoft, so general disclaimers apply. Nevertheless, one of the first things you may notice is this.

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.

9xyz  -  4yz  -  6xyz  -  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.

9xyz  -  4yz  -  6xyz  -  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:

with(LinearAlgebra):
for N from 5 to 9 do
  A := RandomMatrix(2^N, 2^N+1,generator=-10^5..10^5):
  TIMER := time(GaussianElimination(A...

This is a long shot, but I think Maplesoft should open up its bug database and allow MaplePrimes users to vote up or down on bugs, reddit style. This would provide direct feedback about which bugs really affect people. Behind the scenes you could cross-reference the votes with account data to get all kinds of useful information: like what bugs disproportionally affect new users, or what bugs annoy experienced Maple users the most, etc. This would allow you to focus attention...

"I've seen this element before..." Often we are faced with the problem of building up sets incrementally, by removing pieces one at a time from a larger whole. The bottlenecks in this case are usually: 1) adding a small set X to a large set S (copies S and X, making this ~O(|S|+|X|)) 2) removing elements of the large set S from the small set X (binary search: |X|*log(|S|)) A classic example of this is a breadth-first-search. We start at one vertex of a graph and in each iteration we add the set of new neighbors X to the set of vertices S that have already been found. We can make this more useful by making the program return the sets of new neighbors found in each iteration, that is, the sets of vertices that are distance 1, 2, 3, etc. from the initial vertex.

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.

This is not so much a suggestion (I'm not sure if you should change it) but edited blog posts are booted off the front page. I edit sentence missing words and poor grammar and now it gone :)

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.