This is the file 00README.libfac for version 0.3.2 of Singular-libfac. ######### What is Singular-libfac? Singular-libfac is an extension to Singular-factory (see the Singular-factory documentation for details about Singular-factory and what it does; look at REQUIREMENTS how to get Singular-factory), which implements factorization of polynomials over finite fields and algorithms for manipulation of polynomial ideals via the characteristic set methods (e.g., calculating the characteristic set and the irreducible characteristic series). Note: Singular-libfac is just beta-code (as long version is < 1.0.0). There are bugs, I think. Please help to test this code! Submit a bug-report if you found a bug! ######### Copyright ##################### the Copyright is given in the file COPYING ######### REQUIREMENTS ################### * You need the library Singular-factory, which is part of Singular, to compile this code. Get it from ftp://www.mathematik.uni-kl.de/pub/Math/Singular/Factory or http://www.mathematik.uni-kl.de/ftp/pub/Math/Singular/Factory * gcc 2.7.2 ( earlier versions of gcc *may* work as well as any other ANSI C++ compiler; it is reported that gcc 2.6.3 works also, but beware of gcc 2.7.0; it has some serious C++ bugs ) * GNU Make version 3.74 or above ( earlier versions of GNU make *may* work ) ######### INSTALLATION ################### Using configure For the library type: configure [--with-debug] [--with-Singular] [--includedir=path-to-factory.h] make this will produce libfac.a or libsingfac.a (depending on --with-Singular). The only difference between libfac.a and libsingfac.a is: we don't instantiate any templates for libsingfac.a. If you want to produce a test file, type: configure [--with-debug] [--libdir=path-to-libcf.a] [--includedir=path-to-factory.h] make tests this will produce libfac.a and a binary called test. "test" is then used to test some examples for factorization. If you have found a bug in an unmodified version (beside the KNOWN BUGS, see KNOWN BUGS section later), *please* email me: mmessollen@web.de Please include the characteristic and the ideal(s)/polynomial(s) you tried as well as the factoryversion you used (Best to include all your input!). As I am no longer at the university, please allow some days for an answer. Have fun! Michael Messollen ( mmessollen@web.de ) ##### I would like to thank Dongming Wang who showed me the power of the Characteristic Set methods and from whom I learned a lot about this topic. If you want to learn about characteristic sets, the next is a good point to start with: Dongming Wang: An Implementation of the Characteristic Set Method in Maple. In: Automated Practical Reasoning: Algebraic Approaches (J. Pfalzgraf and D. Wang, eds.), Springer-Verlag, Wien-New York, 1995, pp. 187-201. ########### KNOWN BUGS ############################ o The irreducible characteristic series stuff doesn't work for some problems. You will get a warning: "Factorization over algebraic function field required!" if this program needs factorization over an algebraic function field, which is not yet implemented (but I'm working on it). Don't trust the result you'll get in such a case!!!!!! Since version 0.3.0 this problem is gone. (or should be :-) ) o The performance of the irreducible characteristic series stuff heavily depends on the ordering of the variables in some cases. No (nearly) optimal ordering of the variables is chosen automatically, right now. E.g.: if your ideal is (t^10-x, t^31-t^6-t-y, t^8-z) and you choose the variable ordering with t > z > y > x, the calculation of the irreducible characteristic series will take hours; if you choose t as the variable with the lowest level, you will get the answer immediately (the ideal is an irreducible characteristic series with the ordering z > y > x > t ). I am thinking about the problem how to choose the ordering automatically. Since version 0.2 of the library: (There is now a function: Varlist neworder(const CFList & PolyList ), which returns a list of heuristically optimal reordered variables; if you use the library for programming purpose, look at factor.h how to use this function in your code) For users of Macaulay2 and/or Singular: look at the documentation of the respective program, if and how this is incorporated. o Factorization is slow for large polynomials. There are mainly two reasons for this: a) the factorization algorithm is shipped with no "tricks" yet. (I'm working on that, but it heavily depends on b) ) b) factory has an extremely slow GCD-algorithm for the case of characteristic p>0 ( people are working on it ) There will be a quite different, faster factorization algorithm in the future. Problems will be fixed in a later version of libfac . ######### Changes: Version coding scheme: major.minor.bugfixnumber e.g.: 0.1 major=0 minor=1 no bugfixnumber (no bugfix incorporated) V0.1 o Initial version for alpha-testers V0.2 o Added neworder(..) and reorder(..) for IrrCharSeries o Added external strings (in factor/version.cc): libfac_name - the name of the game libfac_version - the version number libfac_date - the date libfac_version was released libfac_author - who wants to know? o added support for factorization of homogeneous polynomials (in factor/homogfactor.cc), reorganized code in factor/Factor.cc and factor/Factor.h o added files factor/debug.cc, factor/debug.h, factor/timing.h; mainly for internal use V0.2.1 o changed lc == 1 to lc == unit in choose_mainvar (factor/Factor.cc) o changed cerr and cout messages for use with Singular (all .cc files) (why the hell don't they use libiostream?) o added configure -- basics only; (old)Makefile changed to Makefile.dist (if nothing works...) Makefile produced with configure uses GNU coding standards o released Apr 25 1997 V0.2.2 o Added ranlib in Makefile.in after installing - Sun's seem to need it o Put -I. before CPPFLAGS in Makefile.in o hardcoded ./install-sh and ./mkinstalldirs in Makefile.in for INSTALL; some machines have a broken install (e.g. HP ) commented out the search for AC_PROG_INSTALL in configure.in o Internal note: Singular now contains definitions from class.cc and tmpl_inst.h in claptmpl.cc o released May 15 1997 V0.2.3 o Added factor/interrupt.cc and interrupt.h to support interrupting calculations: We define a global variable "libfac_interruptflag" in factor/version.cc which, if not zero, interrupts the ongoing calculation. Factorize() will then return an empty list (CFFList), IrrCharSeries will return an empty list of lists (ListCFList). Modified: factor/Factor.cc and charset/charset.cc for this purpose. o version for Macaulay2-Testers o released May 28 1997 V0.2.4 o Changed factor/SqrFree.cc (SqrFreed): Have to interchange variables if one derivative is zero but not all (e.g. no p'th power) example: (y^12+x^10)^2 mod 5 Internal note: have to look at SqrFreeTest!! o Changed factor/Factor.cc (Factorize): multiplied exponent of factors into Output (should be one if Sqrfree doesn't fail); this is for security only (and should be removed later..) o Changed factor/helpstuff (myappend): added support for lists with multiple copies of one element (this doesn't happen for this algorithms... but you never know) o Changed factor/interrupt.{cc|h}: Removed interrupt.cc; added (inline) code to interrupt.h; factor.h will now define the external variable "libfac_interruptflag" Doesn't any longer issue any message about user-interrupt - the CA-System, which has control, should warn user that calculation is aborted. Removed libfac_messageflag from factor/version.cc o Summary: removed: factor/interrupt.cc changed: factor/SqrFree.cc factor/Factor.cc factor/helpstuff.cc Makefile.in configure.in factor/interrupt.h factor.h factor/version.cc o Internal note: something changed in unvivariate factorization over extension fields from factory-1.2b to 1.2c: same polynomial now uses 4 to 12 times longer to factor! Perhaps it's this new random generator? o released May 30 1997 V0.3.0a o changed configure.in: will not override CFLAGS or CXXFLAGS if set in the environment o added new functionality in charset/algfacor.{cc/h} : now we should be able to factorize over any field needed for the charset-algorithm. (Internal note: perhaps there are still problems for the char=0 case because of the factory implementation vs. gmp) o for this, changed charset/csutil.{cc/h} and charset/charset.{cc/h} o include #include in file.cc for some CC's o Internal note: need more interrupt handles enabled; set up test examples for char=0 and char>0; o released Jun 25 1997 V0.3.0b o implemented Tragers algorithm; this is now the default used in charsets (file: charsets/alg_factor.cc) o for char=0 case there are some problems with factory; for char=p there seems to be an internal factory memory-problem in some cases o released Sep 11 1997 V0.3.1 o now ready for cygwin32 o released Jan 15 1998 V0.3.2 o New Copyright o released Jan 31 2001