how to speed up some lisp code?

From: John H Palmieri (palmieri_at_math.washington.edu)
Date: 02/18/04 

Date: Wed, 18 Feb 2004 13:50:55 -0800

I'm a mathematician, and I want to do some computations (using lisp,
specifically Allegro, since that's what we have installed). In fact,
I have written code for doing the things I want, but it's too slow, so
now I would like advice on how to speed things up. I'll explain what
sort of things I'm working with, and I'm wondering about good ways to
deal with them. I think my main question is, how should I represent
each sort of structure? For each data type, should I use defstruct
or defclass, or just represent it as a list, or an alist, or a hash
table?

(By the way, I know some lisp, mainly from emacs lisp hacking, but I
am almost a beginner. When it comes to writing fast code, I am
certainly a beginner. Please keep this in mind when giving advice:
any suggestion, no matter how simple, might be helpful, because I
might have missed it.)

I'm using a data type I'll call a "monomial": these are sorted lists
of non-negative integers. So far, the lists have length at most 7 or
8, but if I can speed things up, I'll want to go up to 20, or more.
The integers in the lists are small: less then 200. Right now, I'm
representing these as lists. (I played around with representing them
as integers: the list (a b c ...) gets translated into an integer
where a is the left-most bunch of bits, then b is the next bunch, and
so on. I was hoping that since I could use arithmetic operations
instead of list operations, and since I could use = instead of equal
for comparison, it would speed things up, but it didn't. Maybe I
didn't do it well. I don't see any advantage in using bit-vectors,
but I haven't tried, and you could try to persuade me if you feel
differently...)

I'm also using a data type I'll call a "polynomial": these are sets of
monomials. Almost always, I want them to be sorted (by lexicographic,
a.k.a. "dictionary," ordering). These could have thousands of monomials
in them. Right now, I'm using lists for these, as well -- probably a
bad choice, but what should I use instead? (For example, should I use
something which lends itself well to sorting?)

I'm also using a data type I'll call a "matrix": these are alists of
polynomials, where the key is a positive integer, and for large parts
of the computation, I want them sorted by key. They could have
hundreds, or maybe thousands, of terms in them. Right now, I'm using
alists for these (and using (sort matrix #'< :key #'car) somewhat
frequently).

The sorts of things I need to do with monomials:
  - test for equality
  - test for "admissibility", and correct if it's inadmissible. A
    monomial (a b c d ... ) is admissible if 2a >= b, 2b >= c, ... If
    it's not admissible, there is a method for fixing that, which
    replaces the inadmissible monomial with a polynomial: if 2b < c,
    then use a formula to turn (b c) into a list of other terms
    (x1 y1), (x2 y2), ..., and then replace (a b c d ...) with
    (a x1 y1 d ...), (a x2 y2 d ...), .... (I'm constructing these
    new monomials with append, which may be slow? I could try to
    rewrite using nconc, but it might be annoying.) Then check each of
    these new monomials for admissibility, and continue until done.
    Because of the nature of the formula, this process does in fact
    terminate.

    (I haven't told you the formula, but here's an example: (1 2 8) is
    inadmissible, and (2 8) equals ((5 5) (4 6)). This turns (1 2 8)
    into ((1 5 5) (1 4 6)). (1 5 5) and (1 4 6) are both
    inadmissible, but (1 5) equals (3 3), and (3 3 5) is admissible;
    also, (1 4) equals (2 3), and (2 3 6) is admissible. So (1 2 8)
    equals ((3 3 5) (2 3 6)).)

The sorts of things I need to do with polynomials:
  - add two polynomials, mod 2. That is, do (set-exclusive-or POLY1 POLY2).
  - given a polynomial P, find all monomials in P which end in an odd
    number.
  - given a polynomial P, find all monomials in P which don't consist
    entirely of odd numbers.

The sorts of things I need to do with matrices:
  - add a pair (a.k.a., a "row") (key . poly) to a matrix
  - find a row with a given key
  - switch rows: that is, given a matrix containing (I . P) and (J . Q),
    return a matrix which is equal except it has (I . Q) and (J . P).
  - add rows. That is, if a matrix has rows (I . P) and (J . Q),
    return a matrix which has rows (I . P) and (J . (add-poly P Q)).
  - loop through the rows in increasing order of their key. 

-- 
J. H. Palmieri
Dept of Mathematics, Box 354350    mailto:palmieri@math.washington.edu
University of Washington           http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350

Relevant Pages

  • Re: how to speed up some lisp code?
    ... polynomials are represented as a defstruct with a field that contains the ... > The integers in the lists are small: ... > The sorts of things I need to do with monomials: ... > The sorts of things I need to do with polynomials: ...
    (comp.lang.lisp)
  • Re: how to speed up some lisp code?
    ... time when I need to compare monomials of different lengths. ... Does equal traverse the lists, ... (cons -1 MONO) ... consider storing the polynomials backwards (least ...
    (comp.lang.lisp)
  • Re: Number Theory problem: seeking Calculus example
    ... polynomials, and ask whether all of this information ... The list of references in this paper is the most ... mentioned in the following two lists of well known ... it seems that a group of mathematicians ...
    (sci.math)
  • Dominance Tree Sorts
    ... "Dominance tree sorts" is a neologism. ... An algorithm is an efficient dominance tree construction ... dominance lists. ...
    (comp.programming)
  • Dominance Tree Sorts
    ... "Dominance tree sorts" is a neologism. ... An algorithm is an efficient dominance tree construction ... dominance lists. ...
    (comp.theory)