source: git/factory/libfac/00README @ 741bb9

spielwiese
Last change on this file since 741bb9 was 16055bd, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: move libfac into factory
  • Property mode set to 100644
File size: 9.2 KB
Line 
1This is the file 00README.libfac for version 0.3.2 of Singular-libfac.
2
3######### What is Singular-libfac?
4Singular-libfac is an extension to Singular-factory
5(see the Singular-factory documentation for details about Singular-factory
6and what it does; look at REQUIREMENTS how to get Singular-factory),
7which implements factorization of polynomials over finite fields and algorithms
8for manipulation of polynomial ideals via the characteristic set methods
9(e.g., calculating the characteristic set and the irreducible characteristic
10series).
11
12Note: Singular-libfac is just beta-code (as long version is < 1.0.0).
13There are bugs, I think. Please help to test this code!
14Submit a bug-report if you found a bug!
15
16######### Copyright #####################
17the Copyright is given in the file COPYING
18
19######### REQUIREMENTS ###################
20* You need the library Singular-factory, which is part of Singular, to compile
21this code. Get it from
22  ftp://www.mathematik.uni-kl.de/pub/Math/Singular/Factory  or
23  http://www.mathematik.uni-kl.de/ftp/pub/Math/Singular/Factory
24 
25* gcc 2.7.2 ( earlier versions of gcc *may* work as well as any other ANSI C++
26  compiler; it is reported that gcc 2.6.3 works also, but beware of gcc 2.7.0;
27  it has some serious C++ bugs )
28
29* GNU Make version 3.74 or above ( earlier versions of GNU make *may* work )
30
31######### INSTALLATION ###################
32Using configure
33For the library type:
34  configure [--with-debug] [--with-Singular] [--includedir=path-to-factory.h]
35  make
36this will produce libfac.a or libsingfac.a (depending on --with-Singular).
37The only difference between libfac.a and libsingfac.a is: we don't instantiate
38any templates for libsingfac.a.
39
40If you want to produce a test file, type:
41  configure [--with-debug] [--libdir=path-to-libcf.a] [--includedir=path-to-factory.h]
42  make tests
43this will produce libfac.a and a binary called test. "test" is then used to
44test some examples for factorization.
45
46 If you have found a bug in an unmodified version (beside the KNOWN BUGS, see
47KNOWN BUGS section later), *please* email me: mmessollen@web.de
48Please include the characteristic and the ideal(s)/polynomial(s) you tried as
49well as the factoryversion you used (Best to include all your input!).
50
51As I am no longer at the university, please allow some days for an answer.
52
53Have fun!
54 Michael Messollen ( mmessollen@web.de )
55
56#####
57I would like to thank Dongming Wang <Dongming.Wang@imag.fr> who showed me the
58power of the Characteristic Set methods and from whom I learned a lot about
59this topic.
60If you want to learn about characteristic sets, the next is a good point
61to start with:
62    Dongming Wang:
63    An Implementation of the Characteristic Set Method in Maple.
64    In: Automated Practical Reasoning: Algebraic Approaches
65    (J. Pfalzgraf and D. Wang, eds.), Springer-Verlag,
66    Wien-New York, 1995, pp. 187-201.
67
68
69########### KNOWN BUGS ############################
70o The  irreducible characteristic series stuff doesn't work for some problems.
71  You will get a warning:
72         "Factorization over algebraic function field required!"
73  if this program needs factorization over an algebraic function field, which
74  is not yet implemented (but I'm working on it).
75  Don't trust the result you'll get in such a case!!!!!!
76Since version 0.3.0 this problem is gone. (or should be :-) )
77
78o The performance of the irreducible characteristic series stuff heavily
79  depends on the ordering of the variables in some cases. No (nearly) optimal
80  ordering of the variables is chosen automatically, right now.
81  E.g.: if your ideal is (t^10-x, t^31-t^6-t-y, t^8-z) and you choose the
82  variable ordering with t > z > y > x, the calculation of the irreducible
83  characteristic series will take hours; if you choose t as the variable with
84  the lowest level, you will get the answer immediately (the ideal is an
85  irreducible characteristic series with the ordering z > y > x > t ).
86  I am thinking about the problem how to choose the ordering automatically.
87Since version 0.2 of the library:
88(There is now a function: Varlist neworder(const CFList & PolyList ),
89 which returns a list of heuristically optimal reordered variables;
90 if you use the library for programming purpose, look at factor.h how to
91 use this function in your code)
92For users of Macaulay2 and/or Singular: look at the documentation of the
93respective program, if and how this is incorporated.
94
95o Factorization is slow for large polynomials. There are mainly two reasons
96  for this:
97   a) the factorization algorithm is shipped with no "tricks" yet. (I'm working
98      on that, but it heavily depends on b) )
99   b) factory has an extremely slow GCD-algorithm for the case of
100      characteristic  p>0 ( people are working on it )
101  There will be a quite different, faster factorization algorithm in the
102  future.
103
104Problems will be fixed in a later version of libfac .
105
106######### Changes:
107Version coding scheme: major.minor.bugfixnumber
108          e.g.: 0.1 major=0 minor=1 no bugfixnumber (no bugfix incorporated)
109
110V0.1    o Initial version for alpha-testers
111
112V0.2    o Added neworder(..) and reorder(..) for IrrCharSeries
113        o Added external strings (in factor/version.cc):
114            libfac_name     - the name of the game
115            libfac_version  - the version number
116            libfac_date     - the date libfac_version was released
117            libfac_author   - who wants to know?
118        o added support for factorization of homogeneous polynomials (in
119          factor/homogfactor.cc),
120          reorganized code in factor/Factor.cc and factor/Factor.h
121        o added files factor/debug.cc, factor/debug.h, factor/timing.h;
122          mainly for internal use
123
124V0.2.1  o changed lc == 1 to lc == unit in choose_mainvar (factor/Factor.cc)
125        o changed cerr and cout messages for use with Singular (all .cc files)
126          (why the hell don't they use libiostream?)
127        o added configure -- basics only; (old)Makefile changed to
128          Makefile.dist (if nothing works...)
129          Makefile produced with configure uses GNU coding standards
130        o released Apr 25 1997
131
132V0.2.2  o Added ranlib in Makefile.in after installing - Sun's seem to need it
133        o Put -I. before CPPFLAGS in Makefile.in
134        o hardcoded ./install-sh and ./mkinstalldirs in Makefile.in for
135          INSTALL; some machines have a broken install (e.g. HP )
136          commented out the search for AC_PROG_INSTALL in configure.in
137        o Internal note: Singular now contains definitions from class.cc and
138          tmpl_inst.h in claptmpl.cc
139        o released May 15 1997
140
141V0.2.3  o Added factor/interrupt.cc and interrupt.h to support interrupting
142          calculations: We define a global variable "libfac_interruptflag"
143          in factor/version.cc which, if not zero, interrupts the ongoing
144          calculation. Factorize() will then return an empty list (CFFList),
145          IrrCharSeries will return an empty list of lists (ListCFList).
146          Modified: factor/Factor.cc and charset/charset.cc for this purpose.
147        o version for Macaulay2-Testers
148        o released May 28 1997
149
150V0.2.4  o Changed factor/SqrFree.cc (SqrFreed): Have to interchange variables
151          if one derivative is zero but not all (e.g. no p'th power)
152          example: (y^12+x^10)^2 mod 5
153          Internal note: have to look at SqrFreeTest!!
154        o Changed factor/Factor.cc (Factorize): multiplied exponent of factors
155          into Output (should be one if Sqrfree doesn't fail); this is for
156          security only (and should be removed later..)
157        o Changed factor/helpstuff (myappend): added support for lists with
158          multiple copies of one element (this doesn't happen for this
159          algorithms... but you never know)
160        o Changed factor/interrupt.{cc|h}: Removed interrupt.cc; added (inline)
161          code to interrupt.h; factor.h will now define the external variable
162          "libfac_interruptflag"
163          Doesn't any longer issue any message about user-interrupt - the
164          CA-System, which has control, should warn user that calculation is
165          aborted. Removed libfac_messageflag from factor/version.cc
166        o Summary: removed: factor/interrupt.cc
167                   changed: factor/SqrFree.cc factor/Factor.cc
168                            factor/helpstuff.cc Makefile.in configure.in
169                            factor/interrupt.h factor.h factor/version.cc
170        o Internal note: something changed in unvivariate factorization over
171          extension fields from factory-1.2b to 1.2c: same polynomial now uses
172          4 to 12 times longer to factor! Perhaps it's this new random
173          generator?
174        o released May 30 1997
175
176V0.3.0a o changed configure.in: will not override CFLAGS or CXXFLAGS if set in
177          the environment
178        o added new functionality in charset/algfacor.{cc/h} :
179          now we should be able to factorize over any field needed for the
180          charset-algorithm. (Internal note: perhaps there are still problems
181          for the char=0 case because of the factory implementation vs. gmp)
182        o for this,  changed charset/csutil.{cc/h} and charset/charset.{cc/h}
183        o include #include <file.h> in file.cc for some CC's
184        o Internal note: need more interrupt handles enabled;
185                         set up test examples for char=0 and char>0;
186        o released Jun 25 1997
187
188V0.3.0b o implemented Tragers algorithm; this is now the default used in
189          charsets (file: charsets/alg_factor.cc)
190        o for char=0 case there are some problems with factory;
191          for char=p there seems to be an internal factory memory-problem in
192          some cases
193        o released Sep 11 1997
194
195V0.3.1  o now ready for cygwin32
196        o released Jan 15 1998
197
198V0.3.2  o New Copyright
199        o released Jan 31 2001
Note: See TracBrowser for help on using the repository browser.