------------------------------------------------------------------ klpol - for computations of type A Kazhdan-Lusztig polys Version - 1.0 - June 09, 2002 Copyright (C) 2002 Gregory S. Warrington email: gwar@alumni.princeton.edu ------------------------------------------------------------------ This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. ------------------------------------------------------------------ Table of Contents: 0 - Intro I - Running the program II - User interface III - The Innards IV - To do --------- 0. Intro --------- I consider this a "Version 1.0" release because it performs the stated objective - it computes type A KL polys (correctly) in a jiffy. It also has a passable user interface and won't crash if you sneeze at it. However, there are many things that stand to be improved and you can probably find input that will crash it. ----------------------- I. Running the program ----------------------- There are at least three possible ways to run klpol. For the second and third ways (the only possible at this point), you will need a working java runtime environment. If you don't know how to do this, remember, google is your friend. 1. (not yet). As a C program. It compiles under gcj, but crashes mysteriously. Let me know if you're interested in a C version and I'll try to track down the problem (hopefully singular :). 2. klpol is a trivial bash script bash. You may want to configure it in three ways: 0. Point to where bash actually lives 1. attach the path to your copy of java 2. modify the memory allocated to klpol. Depending on your java, the syntax may or may not be correct as given. 3. As a jar file. If you're not interested in the innards, the easiest thing to do is to grab a jar file and run it (on linux) as java -jar klpol.122.jar (for java 1.2) java -jar klpol.133.jar (for java 1.3 - might work for 1.4 too) (remember: you can put the memory flags here) Caveats: 1) I know nothing about windows. Do text-based java programs work out-of-the-box on windows? I don't know. 2) I haven't been careful about memory. If you don't have much, you'll probably run out. You can tweak KLPOL_STORE_LIMIT (currently set to a generous 18) and see if that helps. Or you can try inserting a call to clear the hashmap when stuff gets low. ------------------- II. User interface ------------------- The user interface should basically be self-explanatory, though there are a few aspects that require comment: [C]lear hash: Every time a KL polynomial is requested, klpol checks if it has the answer squirreled away. If you would like to make the program forget all of these polynomials it knows, choose this option. [R]eset stats: You can have the program print the following statistics after each polynomial you request: - Total calculated: The number of polynomials it actually calculated. - Total requested: The number it was asked to compute. The difference between this and the number calculated is due to the program using its hash table. - Total reduced: Every time a polynomial is requested, the klpol checks to see if it can be reduced using the flattening operator. This statistic keeps track of that. Go ahead, turn off flattening (see "The innards") and see how these statistics and your running time are affected. [O]ptions: flatten pairs - does the flattening mentioned above. pick generators - currently unimplemented display progress - the standard recursion consists of pxw = term1 + term2 - (big sum). if this is on, klpol will print a "." when each of term1 and term2 have been computed. Then it will print the number of terms in (big sum). Then it prints a "." for each term of (big sum) that has been computed. This is a poor progress meter as it takes a long time for the first "." to show up. print statistics - displays the stats described above. print 0-1 ce's - if klpol finds a counterexample to the 0-1 Conjecture, it lets you know. This conjecture is false, btw, by the end of June, you should be able to read about it at: http://front.math.ucdavis.edu/search?a=Warrington&t=&q=&c=&n=40&s=Listings compute cell - currently unimplemented. ---------------- III. The innards ---------------- The program is divided into eight .java files (each comprising a class). They are lightly documented and somewhat organized. I don't really recommend that you muck around in the code, but suit yourself. Here is a brief description of each: APerm - wrapper for a permutation along with auxiliary information such as descent sets and Coxeter length. Byol - wrapper for arrays of bytes so we can pop them into hashes. EP - procedures for computing extremal pairs. i.e., given w, we often only care about those x <= w such that 1. sx < x => sw < w and 2. xs < x => ws < w. IO - my feeble attempts at dealing with I/O. IPoly - procedures for interpreting arrays as polynomials KLPol - the guts of the K-L polynomial calculation as given by the standard recurrence in Kazhdan and Lusztig's original paper. The major modification to the standard algorithm is the use of "flattening". This helps the speed a lot. Check out http://front.math.ucdavis.edu/math.AG/0102168 for an explanation of this technique. MainKLP - user interface OLine - utility functions for arrays of bytes OLPair - wrapper for pairs of permutations Shol - wrapper for array of ints -------- IV. Todo -------- be more careful about memory document code more carefully improve flexibility of user interface allow better output to files