source: git/libfac/00README @ e89e56

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 #####################
This software is copyrighted by Michael Messollen <mmessollen@web.de>.
    (c) 1996 Michael Messollen <michael@math.uni-sb.de>
    (c) 2000 Michael Messollen <mmessollen@web.de>

This software is copyrighted but you are allowed to distribute it freely in its
unmodified version (as source or binary), as long as this copyright notice 
accompanies your distribution.
If you modify the sources of this software, you are allowed to distribute this
modified version, as long as this copyright notice accompanies your 
distribution and you state anywhere in this copyright notice that you modified
this version of the software.

But be aware: USE THIS SOFTWARE AT YOUR OWN RISK (SEE DISCLAIMER) !

######### DISCLAIMER #####################

  IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY
  FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
  DERIVATIVES THEREOF, EVEN IF THE AUTHOR HAS BEEN ADVISED OF THE
  POSSIBILITY OF SUCH DAMAGE.

  THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
  IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAVE
  NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
  MODIFICATIONS.

######### 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 ###################
A) 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.

B) Using Makefile.dist  
**** Since version 0.3.0 this is no longer supported ****
**** Get an earlier version and patch Makefile.dist for your needs, ****
**** or, better, use configure.


 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 <Dongming.Wang@imag.fr> 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 <file.h> 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