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