Re: how to speed up some lisp code?
From: R. Scott McIntire (mcintire_charlestown_at_comcast.net)
Date: 02/19/04
- Next message: todd english: "new to lisp and a litle confused about..."
- Previous message: André Thieme: "Indention"
- In reply to: John H Palmieri: "how to speed up some lisp code?"
- Next in thread: John H Palmieri: "Re: how to speed up some lisp code?"
- Reply: John H Palmieri: "Re: how to speed up some lisp code?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 18 Feb 2004 21:17:54 -0500
I have a package, rsm.mpoly, at the site
http://sourceforge.net/projects/com-lisp-utils
that models multivariate polynomials.One can compute with polynomials with
coefficients over the Reals, Complex, or Z mod n. They can be ordered with
lex or deglex ordering. Operations currently supported are addition,
multiplication, raising a polynomial to an integer power - which will be
fast if it is over Z mod n. There are functions for returning the leading
power, term, and coefficient under the current ordering. Multivariate
polynomials are represented as a defstruct with a field that contains the
non zero coefficients and powers.
Example:
3 x1^2 x2 x3^4 + x1 x2^2 x3
becomes
((3 #(2 1 4)) (1 (1 2 1)))
This is probably not what you need but it might be useful to look at the
code for ideas. Two interesting features used are: a BOA-constructor and the
use of dynamics variables for efficiency.
-R. Scott McIntire
"John H Palmieri" <palmieri@math.washington.edu> wrote in message
news:s5twu6k12gw.fsf@zeno1.math.washington.edu...
> 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
- Next message: todd english: "new to lisp and a litle confused about..."
- Previous message: André Thieme: "Indention"
- In reply to: John H Palmieri: "how to speed up some lisp code?"
- Next in thread: John H Palmieri: "Re: how to speed up some lisp code?"
- Reply: John H Palmieri: "Re: how to speed up some lisp code?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
