source: git/factory/README @ 17b1f3

spielwiese
Last change on this file since 17b1f3 was d916c6, checked in by Hans Schoenemann <hannes@…>, 13 years ago
3-1-2 git-svn-id: file:///usr/local/Singular/svn/trunk@13476 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 21.0 KB
Line 
1
2
3  --- This `README' file corresponds to Singular-Factory version 3.1 ---
4
5
6                  README file for Singular-Factory
7                  ================================
8
9NOTE: The copyright of Singular-Factory is described in the
10      file COPYING
11
12Overview
13========
141.  What is Factory?
152.  Comments, Questions, Bug Reports
163.  Installation
174.  Distribution
185.  Prerequisites
196.  Memory Manager
207.  Stream IO
218.  Diagnostic Messages
229.  GF(q) Tables
2310. A Note on Singular
2411. Configure Options, Dependencies
2512. Linking Factory with Your Application
2613. Factory Template Instantiation
2714. Documentation
2815. Examples and Tests
2916. Editing Factory
3017. Files in the Distribution
31
32
331. What is Factory?
34===================
35  Factory is a C++ class library that implements a recursive representation
36of multivariate polynomial data.  It is being developed by Ruediger Stobbe
37and Jens Schmidt at the University of Kaiserslautern as an independent and
38self-contained part of the computer algebra system Singular (developed by
39G.-M. Greuel, G. Pfister and H. Schoenemann).
40
41  Factory handles sparse multivariate polynomials over different
42coefficient domains, such as Z, Q and GF(q), as well as algebraic
43extensions over Q and GF(q) in an efficient way.  Factory includes
44algorithms for computing univariate and multivariate gcds, resultants,
45chinese remainders, and several algorithms to factorize univariate
46polynomials over the integers and over finite fields.  Factorization of
47multivariate polynomials over the integers is in beta test stage.
48
49  The interface to the polynomial system of Factory is provided by a single
50class `CanonicalForm' which can deal with elements of the coefficient
51domain as well as polynomials.  Using operator overloading, you can handle
52polynomial data similarly to built-in types such as the machine integers.
53For example, to add two polynomials one simply uses the `+' operator.
54Because of this, Factory is easy to use even if you are not familiar with
55C++ programming.
56
57  There are a couple of utility classes provided by Factory such as lists,
58arrays, polynomial maps, etc.  These make the usage more comfortable.
59
60
612. Comments, Questions, Bug Reports
62====================================
63  Factory is a project in evolution.  That means there is no guarantee that
64Factory is bug free.  I am sure that there are bugs or at least features.
65If you find bugs or if you find a strange behavior of the library, please
66let me know (e-mail: singular@mathematik.uni-kl.de>).
67Comments and questions are welcome, too.
68
69  Factory version 1.2c and newer define an external variable
70`factoryVersion' describing the version of the library.  The external
71variable `factoryConfiguration' (not present in versions 1.2c and 1.3a)
72describes the options Factory has been configured with.  Please include the
73version number and the configuration options in your bug reports.  You may
74either use the UNIX utility `what' to get this information (`what libcf.a')
75or compile and run something similar to this:
76
77  #include <factory.h>
78  main() { cout << factoryVersion << "; " << factoryConfiguration << endl; }
79
803. Installation
81===============
82NOTE: If you have received this Factory distribution together with Singular
83you do not have to worry about compilation or installation at all.  The
84installation procedure for Singular should do everything for you.  For more
85information, see the section "A Note on Singular".
86
87  See the `INSTALL' file for instructions on how to install Factory.  The
88installation procedure on UNIX platforms conforms more or less to the GNU
89standard:
90
91  ./configure; make; make gftables; make install; make installgftables
92
93However, I recommend to read the instructions since there are a lot of
94non-standard options to configure.
95
96  On platforms other than UNIX, where there is no `configure', you have to
97configure and install Factory by hand.  In particular, you have to
98create/edit the files `config.h', `factory.h', `factoryconf.h', and
99`GNUmakefile'.  For Microsoft Windows NT 4.0 with the Microsoft Visual C++
1005.0 compiler there is a preconfigured environment in the `winnt/' directory
101which you may use as an example.  For more information, confer to
102corresponding section in the `INSTALL' file and to the `INSTALL.nt' file in
103the `winnt/' directory.
104
105  In general, this `README' as well as the `INSTALL' file are written for
106UNIX platforms.  However, you may find less specific information on the
107configuration and installation process which is useful for other platforms,
108too.
109
110
1114. Distribution
112===============
113  The latest version of Factory is always available by anonymous ftp from
114
115                www.mathematik.uni-kl.de:/pub/Math/Singular/Factory
116
117The Factory distribution consists of three archives:
118
119o the Factory source code (`factory-<version>.tgz');
120o some preliminary documentation on Factory (`factory-doc-prelim.tgz');
121o Factory GF(q) addition tables (`factory-gftables.tgz', see below).
122
123
1245. Prerequisites
125================
126  You need GNU make to build and install Factory.  Furthermore, I strongly
127recommend to build Factory with GNU CC (version 2.7 or newer).  To build
128Factory and to link your programs with Factory you need the GNU Multiple
129Precision Library (GMP, version 2.0 or newer).  The GMP library is
130available at ftp.gnu.ai.mit.edu or its mirrors.  Alternatively, Factory may
131be linked with the so called small GMP library which comes with the full
132version of Singular (not recommended).
133
134Configure options:
135------------------
136  --with-gmp(=<gmp_inc_path>(,<gmp_lib_path>))
137                          specify where to find the GMP library.
138  --enable-gmp            together with `--with-Singular' means: installation
139                          in process, be graceful when there is no `gmp.h'
140
141  If <gmp_lib_path> is not given, but <gmp_inc_path> is,
142`<gmp_inc_path>/../lib/' is used as <gmp_lib_path>.  If neither
143<gmp_lib_path> nor <gmp_inc_path> is specified, `configure' looks in the
144standard system locations for GMP.
145
146  Furthermore, you may specify the symbolic directory `$(includedir)' for
147<gmp_inc_path>:
148
149  --with-gmp='$(includedir)'
150
151Do not forget the single quotes or otherwise your shell might complain.
152
153  This is useful when Factory is delivered as part of a larger package
154which also provides the GMP library.  In this case, at configuration time
155there would not be any `gmp.h'.  Without this option, Factory's `configure'
156script would exit with an error message.  If this symbolic directory is
157given, the `configure' script does not look for `gmp.h' and `libgmp.a'.
158Rather, it adds the option `-I$(includedir)' to its `$(CXXFLAGS)' and the
159option `-L$(libdir)' to its `$(LDFLAGS)' assuming that at compilation-time
160`gmp.h' and `libgmp.a' will reside in these directories.
161  The option `--enable-gmp' does the same, but it is a special (and ugly)
162gift to Singular, so it may be used with option `--with-Singular' only.
163
164
1656. Memory Manager
166=================
167  You can use one of the memory management tools provided with Factory.
168There are the "new" and the "old" memory manager.  In fact, on some systems
169the old memory management seems to be faster then the new one, but so far
170there have not been systematic timings.  If you configure Factory with
171`--with-memman=no' it will use the standard C++ operators `new'/`delete',
172which is not recommended.
173  You may trace the actions (allocate/free) of the new memory manager by
174enabling memory management debugging.  This produces a *lot* of output.
175
176Configure options:
177------------------
178  --with-memman(=<memman>) specify Factory memory manager.
179                          <memman> is either `old' (default), `new', or `no'.
180  --enable-memdebug=<level> switch on memory management debugging.  Meaningful
181                          with `--with-memman=new' only.  <level> may be either
182                          `no' (default), `normal', or `full'.
183
184
1857. Stream IO
186============
187  For use with other systems which have their own IO routines to print
188polynomials it is possible to switch off Factory's stream IO.  In this
189case, you do not need to link libg++ or libiostream with Factory.
190
191Configure options:
192------------------
193  --disable-streamio      build Factory without stream IO
194
195
1968. Diagnostic Messages
197======================
198Factory has three types of diagnostic messages:
199o Assertions (implemented by the "ASSERT macros" in `assert.h') are used to
200  ensure preconditions before running some algorithm.  A typical example is
201  to test f != 0 before dividing by f.
202o Debug output (implemented by the "DEBOUT macros" in `debug.h'/`debug.cc')
203  is used to trace complex algorithms, e.g. factorization.
204o Timing information may be accumulated and printed using the "TIMING macros"
205  in `timing.h'.
206
207  Since all diagnostic messages are implemented using preprocessor macros,
208they will completely cease when disabled, thus avoiding any impact on
209speed.  For more information, see section "Configuring and building Factory
210for different configurations" in the `INSTALL' file.  By default, all
211diagnostic messages are disabled.
212
213Configure options:
214------------------
215  --enable-assertions     build Factory with assertions activated
216  --enable-timing         build Factory so it will print timing information
217  --enable-debugoutput    build Factory so it will print debugging information
218
219
2209. GF(q) Tables
221===============
222
223NOTE: Since the format of the GF(q) tables changed from Factory Version
2241.2b to Factory Version 1.3a you should get/create them by new!
225
226  Factory uses addition tables to calculate in GF(p^n) in an efficient way.
227
228There are two possibilities to get these tables:
229o get them from the net (`factory-gftables.tgz') where you got Factory
230  from.  The files unpack into a directory `gftables/'.
231o create them with `gengftables' which is a part of Factory.  Building
232  the tables takes quite a while!
233See the `INSTALL' file for more information.
234
235
23610. A Note on Singular
237=====================
238  If you have received this Factory distribution together with Singular you
239do not have to worry about compilation or installation at all.  The
240installation procedure for Singular should do everything for you.  If you
241want to configure/build the package on your own instead of letting
242Singular's `configure' do the work you should:
243
244  ./configure --with-Singular --enable-gmp
245        (or, equivalently: )
246  ./configure --with-Singular --with-gmp='${includedir}'
247
248  Furthermore, you should specify `--prefix' so `make install' will install
249the files in the places where Singular looks for them.  By default, this is
250the top directory of the Singular distribution.  In this case you have to
251specify `--prefix=..'.
252
253  The Singular GF(q) tables are the same as the Factory GF(q) tables.
254However, Singular uses a different naming scheme.  Therefore, a Factory
255configured with `--without-Singular' will not find Singular's GF(q) tables
256as well as a Factory configured with `--with-Singular' will not find the
257GF(q) tables created by gengftables.  But this is not a major drawback
258since Singular is distributed with ready-to-use GF(q) tables.
259
260  The latest version of Singular is always available at
261www.mathematik.uni-kl.de:/pub/Math/Singular.
262
263Configure options:
264------------------
265  --with-Singular         build for use with computer algebra system Singular.
266
267  Except from setting the `#define SINGULAR', this option only changes the
268defaults to: `--with-memman=no --disable-streamio'.
269
270
27111. Configure Options, Dependencies
272===================================
273o do not configure `--with-Singular --with-memman'.  In this case
274  both Singular and the library will try to initialize their own memory
275  management.
276
277o do not configure `--disable-streamio --enable-debugoutput'.  The
278  "DEBOUT macros" need stream IO.
279
280o you may configure `--with-Singular --enable-streamio', but this
281  is not supported by Singular.  You will have to change manually
282  Singular's `Makefile'.  The same is true for `--with-Singular
283  --enable-streamio --enable-debugoutput'.
284
285o you may configure `--with-Singular --enable-timing', but this
286  will not have any visible effect (except from a slightly slower
287  running time) because Singular will not print the timing
288  results.
289
290o `--enable-gmp' has an effect only together with `--with-Singular'
291
292o `--with-memdebug' has an effect only together with
293  `--with-memman=new'
294
295
29612. Linking Factory With Your Application
297=========================================
298  To translate your application you need (apart from your
299application, of course):
300
301o the Factory user interface header file (`factory.h')
302
303  To link your application with Factory you need:
304
305o the Factory library (`libcf.a')
306o unless you configured Factory `--without-memman' you need one of the
307  Factory memory manager libraries (`libcfmem.a')
308
309o the instantiated Factory templates (`ftmpl_inst.o').
310
311o unless you configured Factory `--without-streamio' you need the stream IO
312  libraries.  With GNU CC, you do not need to care about this because they
313  are linked automatically to your application if you call the compiler
314  either as `g++' or as `c++'.  Otherwise, you need to link with library
315  `libiostream.a'.
316o The GNU Multiple Precision Library (`libgmp.a').  See section
317  "Prerequisites" in this file for more information.
318o The standard mathematical library (`libm.a')
319
320  `factory.h', `libcf.a', and `libcfmem.a' are created when you build
321Factory and installed by `make install'.  `libiostream.a', `libgmp.a', and
322`libm.a' should be already installed on your system, otherwise your
323application will fail to link.  `ftmpl_inst.o' is not installed by Factory.
324Instead, its source file `ftmpl_inst.cc' is installed and you have to build
325`ftmpl_inst.o' when you are building your application.  For more
326information on template instantiation and `ftmpl_inst.cc', see the
327following section "Factory Template Instantiation".
328
329  To give an example, look at the following one-shot solution to the
330problem "linking Factory with your application" where the "application" is
331a small test program (`application.cc') from the subdirectory `examples/'
332of the Factory source directory ('\' at the end of a line denotes line
333continuation):
334
335  g++ -c /usr/local/include/templates/ftmpl_inst.cc \
336    -fno-implicit-templates -O2 -fomit-frame-pointer -o ftmpl_inst.o
337  g++ -c application.cc -fno-implicit-templates -O2 -fomit-frame-pointer \
338    ftmpl_inst.o -lcf -lcfmem -lm -lgmp
339
340  This should work fine provided that you installed Factory in a location
341where `g++' may find it (here I have assumed `/usr/local/') and all the
342other files mentioned above are installed properly and where `g++' looks
343for them.
344
345  You may find a small `GNUmakefile' which translates `application.cc' and
346other examples in the `examples/' subdirectory of the Factory source
347directory.  For more information, see the section "Examples and Tests".
348
349
35013. Factory Template Instantiation
351==================================
352  There are a couple of classes provided by Factory such as lists, arrays,
353etc, which may be used to derive new abstract data types from already
354existing ones.  Factory uses them itself, e.g. to return the result of a
355factorization (a list of factors), and you may use them to create new
356derived abstract data types.  These classes are realized using C++
357"templates", which you need to "instantiate" befor you use them (refer to
358some introduction to C++ if you do not know these terms).
359
360  With GNU CC the most reliable way to instantiate templates is to
361
362o explicitely instantiate all necessary templates, and compile with option
363  `-fno-implicit-templates' and to
364o collect all explicit template instantiations in one single file.
365
366  This approach is the one Factory uses.  All object files of the library
367are generated with option `--fno-implicit-templates' and the explicit
368template instantiations are collected in `ftmpl_inst.cc'.  You could
369translate this file using the `make' target `ftmpl_inst.o' (see section
370"Building Factory" in the `INSTALL' file).
371
372  The consequence of this approach: since you may want to add template
373instantiations of Factory's or your own templates after the installation of
374Factory, it is necessary to install `ftmpl_inst.cc' as well as the template
375source files together with the library.  They are automatically installed
376in `$(includedir)/templates/' when you type `make install'.
377
378  To join your own template instantiations with the ones from
379`ftmpl_inst.cc' there are several possibilities:
380
381o you copy `ftmpl_inst.cc' file from the directory where it was installed
382  into your working directory and add your template instantiations after
383  the corresponig comment at the end of the file;
384o you cut the template instantiations from `ftmpl_inst.cc' and paste
385  them into your own template instantiation file.
386
387Both methods suffer from one disadvantage: each time `ftmpl_inst.cc'
388changes in a new version of Factory you will have to redo these steps.  The
389best method therefore is maybe this one:
390
391o you write your own template instantiation file with a
392  `#include <templates/ftmpl_inst.cc>' statement at the beginning of it.
393
394
39514. Documentation
396=================
397  So far there are only preliminary versions of a user/reference manual and
398a tutorial ("A quick start into Factory").  Please do not expect them to
399be error-free or even complete.  For this reason, the documentation is not
400included in the source code archive (`factory-<version>.tgz').  Instead, the
401sources and compiled DVI files reside in `factory-doc-prelim.tgz'. They will
402unpack into a directory `factory-doc-prelim/'.
403
404
40515. Examples and Tests
406======================
407  The directory `examples/' in the Factory source directory contains some
408example applications for Factory and a `GNUmakefile' to build them.  The
409main purpose of the examples is to show how to link applications with an
410installed version of Factory.  This means that you have to install Factory
411before you can build the examples (but it is not necessary to install the
412GF(q) tables).  For the same reason, the `GNUmakefile' is not configured
413automatically by `configure'.  You will have to change some of the
414variables manually.
415
416  Furthermore, you may have a look at `gengftables.cc' in the Factory
417source directory which is another application of the most basic Factory
418features.
419
420  To test whether Factory (including GF(q) tables) has been installed
421properly, use `make' target `installtest'.
422
423
42416. Editing Factory
425===================
426  Parts of Factory are written using GNU Emacs' `folding-mode'.  You may
427load this mode from Emacs with
428
429  M-x load-file RET factory-<version>/bin/folding.el RET
430
431To switch it on, say `M-x folding-mode RET'.  Alternatively, you may load
432`factory-<version>/bin/fold-docu.el' which contains some additional functions
433to fold only the documentation.  If you add the following lines to your
434`.emacs' file, all this would be done automatically for you:
435
436  (load-file "factory-<version>/bin/folding.el")
437  (load-file "factory-<version>/bin/fold-docu.el")
438  (add-hook 'c-mode-common-hook 'folding-mode)
439  (setq fold-fold-on-startup nil
440        fold-mode-marks-alist '((c++-mode "//{{{" "//}}}")))
441  (set-default 'fold-internal-margins nil)
442
443  For more information, see the respective files.
444
445
44617. Files in the Distribution
447=============================
448ChangeLog       - history of changes
449INSTALL         - installation instructions
450NEWS            - new Factory features
451README          - this file
452
453bin/install-sh  - a script version of the BSD `install' program
454bin/makeheader  - creates headers from header templates (`*.template')
455bin/mkinstalldirs - recursive `mkdir'
456bin/folding.el  - Emacs `folding-mode'
457bin/fold-docu.el - some extensions to it
458
459GNUmakefile.in  - master makefile and
460config.h.in     - configuration include file.  Run `configure' to create
461                  `GNUmakefile' and `config.h', resp.
462configure
463configure.in    - `configure' script generated with Autoconf 2.10
464                  from `configure.in'
465
466factory.template
467factoryconf.template - header templates for the user interface header
468                  files.  Run `makeheader' to create `factory.h' and
469                  `factoryconf.h', resp.
470
471ffops.cc
472ffops.h
473gf_tabutil.cc
474gf_tabutil.h
475gfops.cc
476gfops.h
477imm.h
478int_*.cc
479int_*.h         - low level classes and functions
480
481canonicalform.cc
482canonicalform.h
483cf_*.cc
484cf_*.h
485variable.cc
486variable.h      - high level classes and functions.  User interface to
487                  the polynomial (and other) arithmetic.
488
489templates/      - Factory templates
490ftmpl_inst.cc   - template instantiation for Factory templates
491
492fac_*.cc
493fac_*.h         - high level algorithms (factorization, gcd, sqfr
494                  computation, etc.)
495sm_*.c
496sm_*.h          - sparse modular gcd.  Contributed by Marion Bruder
497                  <bruder@math.uni-sb.de>
498
499parseutil.cc
500parseutil.h
501readcf.cc
502readcf.y        - Factory parser to read canonical forms.  `readcf.cc'
503                  translated with Bison 1.18 from `readcf.y'.
504
505gmpext.h
506initgmp.cc      - Factories interface to GNU MP
507singext.cc
508singext.h       - Factories interface to Singular
509
510NTLconvert.*    - some conversion routines for using NTL
511
512memutil.c
513memutil.h       - "old" Factory memory manager
514memman.h
515mm*.c
516mm*.h           - "new" Factory memory manager
517newdelete.cc    - C++ interface to the memory managers
518
519assert.h        - the "ASSERT macros"
520debug.h
521debug.cc        - the "DEBOUT macros"
522timing.h        - the "TIMING macros"
523
524examples/       - some example applications for Factory and a `GNUmakefile'
525                  to build them
526gengftables.cc  - run `gengftables' to create the GF(q) addition tables
527                  necessary to work with Factory
528test_install.cc - a small program to test whether installation has
529                  been successful.  Built and called by `make' target
530                  `installtest'
Note: See TracBrowser for help on using the repository browser.