[57c38e] | 1 | |
---|
| 2 | |
---|
[5f544e] | 3 | --- This `README' file corresponds to Singular-Factory version 4.1 --- |
---|
[57c38e] | 4 | |
---|
| 5 | |
---|
[20e558] | 6 | README file for Singular-Factory |
---|
| 7 | ================================ |
---|
[57c38e] | 8 | |
---|
[20e558] | 9 | NOTE: The copyright of Singular-Factory is described in the |
---|
[ccf43d5] | 10 | file COPYING |
---|
[e4126a] | 11 | |
---|
[57c38e] | 12 | Overview |
---|
[51268e] | 13 | ======== |
---|
[e4126a] | 14 | 1. What is Factory? |
---|
| 15 | 2. Comments, Questions, Bug Reports |
---|
| 16 | 3. Installation |
---|
| 17 | 4. Distribution |
---|
| 18 | 5. Prerequisites |
---|
[f0678b] | 19 | 6. Stream IO |
---|
| 20 | 7. Diagnostic Messages |
---|
| 21 | 8. GF(q) Tables |
---|
| 22 | 9. A Note on Singular |
---|
[f0cd66c] | 23 | 10. Factory Template Instantiation |
---|
| 24 | 11. Documentation |
---|
| 25 | 12. Examples and Tests |
---|
| 26 | 13. Remark on Characteristic Sets |
---|
[6e4bb0] | 27 | 14. Adding new code |
---|
[c86648] | 28 | 15. Nomenclature |
---|
| 29 | 16. Limitations |
---|
[51268e] | 30 | |
---|
| 31 | 1. What is Factory? |
---|
| 32 | =================== |
---|
[57c38e] | 33 | Factory is a C++ class library that implements a recursive representation |
---|
[f0678b] | 34 | of multivariate polynomial data. It was developed by Ruediger Stobbe |
---|
[51268e] | 35 | and Jens Schmidt at the University of Kaiserslautern as an independent and |
---|
| 36 | self-contained part of the computer algebra system Singular (developed by |
---|
[f0678b] | 37 | G.-M. Greuel, G. Pfister and H. Schoenemann) and is now developed by Martin Lee. |
---|
[57c38e] | 38 | |
---|
| 39 | Factory handles sparse multivariate polynomials over different |
---|
| 40 | coefficient domains, such as Z, Q and GF(q), as well as algebraic |
---|
[51268e] | 41 | extensions over Q and GF(q) in an efficient way. Factory includes |
---|
| 42 | algorithms for computing univariate and multivariate gcds, resultants, |
---|
[f0678b] | 43 | chinese remainders, and algorithms to factorize multivariate polynomials |
---|
| 44 | and to compute the absolute factorization of multivariate polynomials with integer |
---|
| 45 | coefficients. |
---|
[57c38e] | 46 | |
---|
| 47 | The interface to the polynomial system of Factory is provided by a single |
---|
[e4126a] | 48 | class `CanonicalForm' which can deal with elements of the coefficient |
---|
| 49 | domain as well as polynomials. Using operator overloading, you can handle |
---|
[57c38e] | 50 | polynomial data similarly to built-in types such as the machine integers. |
---|
[e4126a] | 51 | For example, to add two polynomials one simply uses the `+' operator. |
---|
| 52 | Because of this, Factory is easy to use even if you are not familiar with |
---|
| 53 | C++ programming. |
---|
[57c38e] | 54 | |
---|
| 55 | There are a couple of utility classes provided by Factory such as lists, |
---|
| 56 | arrays, polynomial maps, etc. These make the usage more comfortable. |
---|
| 57 | |
---|
[e4126a] | 58 | 2. Comments, Questions, Bug Reports |
---|
[51268e] | 59 | ==================================== |
---|
| 60 | Factory is a project in evolution. That means there is no guarantee that |
---|
| 61 | Factory is bug free. I am sure that there are bugs or at least features. |
---|
| 62 | If you find bugs or if you find a strange behavior of the library, please |
---|
[8a47d24] | 63 | let me know (e-mail: singular@mathematik.uni-kl.de>). |
---|
[51268e] | 64 | Comments and questions are welcome, too. |
---|
[e4126a] | 65 | |
---|
[bc94b09] | 66 | Factory version 1.2c and newer define an string |
---|
| 67 | `FACTORYVERSION' describing the version of the library. The external |
---|
[e4126a] | 68 | variable `factoryConfiguration' (not present in versions 1.2c and 1.3a) |
---|
| 69 | describes the options Factory has been configured with. Please include the |
---|
| 70 | version number and the configuration options in your bug reports. You may |
---|
| 71 | either use the UNIX utility `what' to get this information (`what libcf.a') |
---|
| 72 | or compile and run something similar to this: |
---|
[57c38e] | 73 | |
---|
[fb1675] | 74 | #include "factory.h" |
---|
[bc94b09] | 75 | main() { cout << FACTORYVERSION << "; " << factoryConfiguration << endl; } |
---|
[57c38e] | 76 | |
---|
[51268e] | 77 | 3. Installation |
---|
| 78 | =============== |
---|
| 79 | NOTE: If you have received this Factory distribution together with Singular |
---|
| 80 | you do not have to worry about compilation or installation at all. The |
---|
| 81 | installation procedure for Singular should do everything for you. For more |
---|
[e4126a] | 82 | information, see the section "A Note on Singular". |
---|
[51268e] | 83 | |
---|
[f0678b] | 84 | For further information on factory's configure options see also ./configure --help. |
---|
[57c38e] | 85 | |
---|
[f0678b] | 86 | The installation procedure on UNIX platforms conforms more or less to the GNU |
---|
| 87 | standard: |
---|
[57c38e] | 88 | |
---|
[f0678b] | 89 | ./configure --without-Singular; make; make check; make install; |
---|
[b7ef56] | 90 | |
---|
| 91 | In general, this `README' as well as the `INSTALL' file are written for |
---|
| 92 | UNIX platforms. However, you may find less specific information on the |
---|
| 93 | configuration and installation process which is useful for other platforms, |
---|
| 94 | too. |
---|
| 95 | |
---|
[51268e] | 96 | 4. Distribution |
---|
| 97 | =============== |
---|
[f0678b] | 98 | The latest stable version of Factory is always available from |
---|
[57c38e] | 99 | |
---|
[f0678b] | 100 | www.singular.uni-kl.de |
---|
[57c38e] | 101 | |
---|
[f0678b] | 102 | For the latest development version visit |
---|
[57c38e] | 103 | |
---|
[f0678b] | 104 | www.github.com/Singular |
---|
[57c38e] | 105 | |
---|
[51268e] | 106 | 5. Prerequisites |
---|
| 107 | ================ |
---|
[a16c0d] | 108 | You need GNU make to build and install Factory. Furthermore, I strongly |
---|
[f0678b] | 109 | recommend to build Factory with GNU CC. To build |
---|
[a16c0d] | 110 | Factory and to link your programs with Factory you need the GNU Multiple |
---|
[f0678b] | 111 | Precision Library (GMP). |
---|
[57c38e] | 112 | |
---|
[a16c0d] | 113 | Configure options: |
---|
[51268e] | 114 | ------------------ |
---|
[f0678b] | 115 | --with-gmp=<path to GMP> enabled by default |
---|
| 116 | |
---|
| 117 | For full functionality NTL (www.shoup.net/ntl) is required. |
---|
[a16c0d] | 118 | |
---|
| 119 | Configure options: |
---|
[51268e] | 120 | ------------------ |
---|
[f0678b] | 121 | --with-ntl=<path to NTL> enabled by default |
---|
[a16c0d] | 122 | |
---|
[f0678b] | 123 | For optimal preformance we recommend to use FLINT (www.flintlib.org) and to use |
---|
| 124 | Singular's memory manager omalloc |
---|
[a16c0d] | 125 | |
---|
[f0678b] | 126 | Configure options: |
---|
| 127 | ------------------ |
---|
| 128 | --with-flint=<path to FLINT> enabled by default |
---|
| 129 | --with-omalloc disabled by default |
---|
| 130 | --with-omalloc-dir=<path to omalloc> |
---|
| 131 | |
---|
| 132 | 6. Stream IO |
---|
[51268e] | 133 | ============ |
---|
| 134 | For use with other systems which have their own IO routines to print |
---|
[f0678b] | 135 | polynomials it is possible to switch off Factory's stream IO. |
---|
[a16c0d] | 136 | |
---|
| 137 | Configure options: |
---|
[51268e] | 138 | ------------------ |
---|
| 139 | --disable-streamio build Factory without stream IO |
---|
[a16c0d] | 140 | |
---|
| 141 | |
---|
[f0678b] | 142 | 7. Diagnostic Messages |
---|
[51268e] | 143 | ====================== |
---|
[a16c0d] | 144 | Factory has three types of diagnostic messages: |
---|
[650f2d8] | 145 | o Assertions (implemented by the "ASSERT macros" in `cf_assert.h') are used to |
---|
[51268e] | 146 | ensure preconditions before running some algorithm. A typical example is |
---|
[a16c0d] | 147 | to test f != 0 before dividing by f. |
---|
[e4126a] | 148 | o Debug output (implemented by the "DEBOUT macros" in `debug.h'/`debug.cc') |
---|
| 149 | is used to trace complex algorithms, e.g. factorization. |
---|
| 150 | o Timing information may be accumulated and printed using the "TIMING macros" |
---|
| 151 | in `timing.h'. |
---|
[a16c0d] | 152 | |
---|
| 153 | Since all diagnostic messages are implemented using preprocessor macros, |
---|
[50901d] | 154 | they will completely cease when disabled, thus avoiding any impact on |
---|
[f0678b] | 155 | speed. By default, all diagnostic messages are disabled. |
---|
[a16c0d] | 156 | |
---|
| 157 | Configure options: |
---|
[51268e] | 158 | ------------------ |
---|
| 159 | --enable-assertions build Factory with assertions activated |
---|
| 160 | --enable-timing build Factory so it will print timing information |
---|
| 161 | --enable-debugoutput build Factory so it will print debugging information |
---|
[a16c0d] | 162 | |
---|
[f0678b] | 163 | 8. GF(q) Tables |
---|
[51268e] | 164 | =============== |
---|
[a16c0d] | 165 | |
---|
[e4126a] | 166 | Factory uses addition tables to calculate in GF(p^n) in an efficient way. |
---|
| 167 | |
---|
[f0678b] | 168 | They can be created with `make gengftables'. Building the tables takes quite |
---|
| 169 | a while! |
---|
[57c38e] | 170 | |
---|
[f0678b] | 171 | 9. A Note on Singular |
---|
[51268e] | 172 | ===================== |
---|
[57c38e] | 173 | If you have received this Factory distribution together with Singular you |
---|
| 174 | do not have to worry about compilation or installation at all. The |
---|
[f0678b] | 175 | installation procedure for Singular should do everything for you. |
---|
[e4126a] | 176 | |
---|
[f0678b] | 177 | 10. Factory Template Instantiation |
---|
[e4126a] | 178 | ================================== |
---|
| 179 | There are a couple of classes provided by Factory such as lists, arrays, |
---|
| 180 | etc, which may be used to derive new abstract data types from already |
---|
| 181 | existing ones. Factory uses them itself, e.g. to return the result of a |
---|
| 182 | factorization (a list of factors), and you may use them to create new |
---|
| 183 | derived abstract data types. These classes are realized using C++ |
---|
[f0678b] | 184 | templates, which are instantiated in one single file namely ftmpl_inst.cc . |
---|
[e4126a] | 185 | |
---|
[f0678b] | 186 | 11. Documentation |
---|
[51268e] | 187 | ================= |
---|
[a16c0d] | 188 | So far there are only preliminary versions of a user/reference manual and |
---|
[e4126a] | 189 | a tutorial ("A quick start into Factory"). Please do not expect them to |
---|
| 190 | be error-free or even complete. For this reason, the documentation is not |
---|
| 191 | included in the source code archive (`factory-<version>.tgz'). Instead, the |
---|
| 192 | sources and compiled DVI files reside in `factory-doc-prelim.tgz'. They will |
---|
| 193 | unpack into a directory `factory-doc-prelim/'. |
---|
[a16c0d] | 194 | |
---|
| 195 | |
---|
[f0678b] | 196 | 12. Examples and Tests |
---|
[51268e] | 197 | ====================== |
---|
[e4126a] | 198 | The directory `examples/' in the Factory source directory contains some |
---|
[f0678b] | 199 | example applications for Factory. |
---|
[e4126a] | 200 | |
---|
[f0678b] | 201 | 'make check' will run some simple test as well. |
---|
[a16c0d] | 202 | |
---|
[f0cd66c] | 203 | 13. Remark on Characteristic Sets |
---|
| 204 | ================================= |
---|
| 205 | Algorithms for manipulation of polynomial ideals via the characteristic set |
---|
| 206 | methods (e.g., calculating the characteristic set and the irreducible |
---|
| 207 | characteristic series) are now incorpareted into factory. |
---|
| 208 | If you want to learn about characteristic sets, the next is a good point |
---|
| 209 | to start with: |
---|
| 210 | Dongming Wang: |
---|
| 211 | An Implementation of the Characteristic Set Method in Maple. |
---|
| 212 | In: Automated Practical Reasoning: Algebraic Approaches |
---|
| 213 | (J. Pfalzgraf and D. Wang, eds.), Springer-Verlag, |
---|
| 214 | Wien-New York, 1995, pp. 187-201. |
---|
| 215 | |
---|
[6e4bb0] | 216 | 14. Adding new code |
---|
| 217 | =================== |
---|
| 218 | If you like to add new code 'foo.cc/foo.h' add 'foo.cc' to 'Makefile.am' under |
---|
| 219 | 'SOURCES' and 'foo.h' under 'factory_headers'. If your new functions should be |
---|
| 220 | available via factory's global interface 'factory.h' add |
---|
| 221 | |
---|
| 222 | /*MAKEHEADER PUBLIC ONLY*/ |
---|
| 223 | foo.h |
---|
| 224 | |
---|
| 225 | to 'factory.template' and enclose the functions in 'foo.h', that you like to |
---|
| 226 | add, by '/*BEGINPUBLIC*/' and '/*ENDPUBLIC*/'. |
---|
[f0cd66c] | 227 | |
---|
[c86648] | 228 | 15. Nomenclature |
---|
| 229 | ================ |
---|
| 230 | Factorization related functions are contained in files with the prefix 'fac'. |
---|
| 231 | Functions operating on CanonicalForm's are contained in files with the prefix |
---|
| 232 | 'cf'. Functions operating on the internal structures of a CanonicalForm are |
---|
| 233 | contained in files with the prefix 'int'. Exceptions are gfops.cc/.h, |
---|
| 234 | ffops.cc/.h, imm.cc/.h as they use intrinsic data types. |
---|
| 235 | |
---|
| 236 | 16. Limitations |
---|
| 237 | =============== |
---|
| 238 | The largest characteristic of a finite field is limited to 536870909. The |
---|
| 239 | number of elements of a finite fields represented by Conway polynomials has to |
---|
| 240 | be < 2^16 (see gfops.cc). |
---|
| 241 | |
---|