1 | This is the file 00README.libfac for version 0.3.2 of Singular-libfac. |
---|
2 | |
---|
3 | ######### What is Singular-libfac? |
---|
4 | Singular-libfac is an extension to Singular-factory |
---|
5 | (see the Singular-factory documentation for details about Singular-factory |
---|
6 | and what it does; look at REQUIREMENTS how to get Singular-factory), |
---|
7 | which implements factorization of polynomials over finite fields and algorithms |
---|
8 | for manipulation of polynomial ideals via the characteristic set methods |
---|
9 | (e.g., calculating the characteristic set and the irreducible characteristic |
---|
10 | series). |
---|
11 | |
---|
12 | Note: Singular-libfac is just beta-code (as long version is < 1.0.0). |
---|
13 | There are bugs, I think. Please help to test this code! |
---|
14 | Submit a bug-report if you found a bug! |
---|
15 | |
---|
16 | ######### Copyright ##################### |
---|
17 | the Copyright is given in the file COPYING |
---|
18 | |
---|
19 | ######### REQUIREMENTS ################### |
---|
20 | * You need the library Singular-factory, which is part of Singular, to compile |
---|
21 | this 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 ################### |
---|
32 | Using configure |
---|
33 | For the library type: |
---|
34 | configure [--with-debug] [--with-Singular] [--includedir=path-to-factory.h] |
---|
35 | make |
---|
36 | this will produce libfac.a or libsingfac.a (depending on --with-Singular). |
---|
37 | The only difference between libfac.a and libsingfac.a is: we don't instantiate |
---|
38 | any templates for libsingfac.a. |
---|
39 | |
---|
40 | If 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 |
---|
43 | this will produce libfac.a and a binary called test. "test" is then used to |
---|
44 | test some examples for factorization. |
---|
45 | |
---|
46 | If you have found a bug in an unmodified version (beside the KNOWN BUGS, see |
---|
47 | KNOWN BUGS section later), *please* email me: mmessollen@web.de |
---|
48 | Please include the characteristic and the ideal(s)/polynomial(s) you tried as |
---|
49 | well as the factoryversion you used (Best to include all your input!). |
---|
50 | |
---|
51 | As I am no longer at the university, please allow some days for an answer. |
---|
52 | |
---|
53 | Have fun! |
---|
54 | Michael Messollen ( mmessollen@web.de ) |
---|
55 | |
---|
56 | ##### |
---|
57 | I would like to thank Dongming Wang <Dongming.Wang@imag.fr> who showed me the |
---|
58 | power of the Characteristic Set methods and from whom I learned a lot about |
---|
59 | this topic. |
---|
60 | If you want to learn about characteristic sets, the next is a good point |
---|
61 | to 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 ############################ |
---|
70 | o 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!!!!!! |
---|
76 | Since version 0.3.0 this problem is gone. (or should be :-) ) |
---|
77 | |
---|
78 | o 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. |
---|
87 | Since 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) |
---|
92 | For users of Macaulay2 and/or Singular: look at the documentation of the |
---|
93 | respective program, if and how this is incorporated. |
---|
94 | |
---|
95 | o 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 | |
---|
104 | Problems will be fixed in a later version of libfac . |
---|
105 | |
---|
106 | ######### Changes: |
---|
107 | Version coding scheme: major.minor.bugfixnumber |
---|
108 | e.g.: 0.1 major=0 minor=1 no bugfixnumber (no bugfix incorporated) |
---|
109 | |
---|
110 | V0.1 o Initial version for alpha-testers |
---|
111 | |
---|
112 | V0.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 | |
---|
124 | V0.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 | |
---|
132 | V0.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 | |
---|
141 | V0.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 | |
---|
150 | V0.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 | |
---|
176 | V0.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 | |
---|
188 | V0.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 | |
---|
195 | V0.3.1 o now ready for cygwin32 |
---|
196 | o released Jan 15 1998 |
---|
197 | |
---|
198 | V0.3.2 o New Copyright |
---|
199 | o released Jan 31 2001 |
---|