PaperlayerView exact revision on arXiv

Source-linked AI summary

FORM version 4.0

J. Kuipers, T. Ueda, J. A. M. Vermaseren, J. Vollinga

arXiv:1203.6543v1cs.SChep-ph

TL;DR

FORM 4.0 addresses users’ need for factorization while extending symbolic manipulation to rational polynomials and other advanced calculations. It adds these capabilities alongside checkpoint backups, open-source availability, and facilities for future extensions.

  • Problem

    Users had missed factorization, while increasingly complex computations required continued extensions to FORM’s symbolic-manipulation capabilities.

  • Method

    FORM 4.0 adds rational-polynomial manipulation, expression factorization, new commands and functions, checkpoint backups, and user-implementable extensions.

  • Results

    FORM 4.0 makes factorization available and provides PolyRatFun for manipulating rational polynomials, while adding many commands and functions.

  • Takeaways & Limitations

    The release supports calculations using significantly different algorithms and enables users to implement their own additions.

  • Takeaways & Limitations

    Backward compatibility remained a development problem, and some version-transition cases still required manual conversion.

Abstract

from arXiv · show

We present version 4.0 of the symbolic manipulation system FORM. The most important new features are manipulation of rational polynomials and the factorization of expressions. Many other new functions and commands are also added; some of them are very general, while others are designed for building specific high level packages, such as one for Groebner bases. New is also the checkpoint facility, that allows for periodic backups during long calculations. Lastly, FORM 4.0 has become available as open source under the GNU General Public License version 3.

1 Introduction

FORM evolved from a fast symbolic manipulation system for large expressions into a more extensible language with broader capabilities and improved version compatibility. Version 4 adds open-source collaboration facilities while preserving compatibility with version 3 programs.

  • FORM was originally designed for symbolic calculations involving Dirac traces, vector dot products, functions, and very large expressions.
  • Development expanded FORM's handling of functions, argument fields, pattern matching, and communication between expressions and input programs.Version 3 introduced $-variables and a rewritten input-processing system that simplified adding commands.
  • Parallel execution developed through ParFORM for networked computers and TFORM for multicore systems, with different communication trade-offs.ParFORM uses MPI across computers and TFORM is multithreaded for multicore computers.
  • Version 4 avoids the earlier transition problems by supporting all version 3 programs, apart from changeable default settings.Old default values can be restored in the setup file.
  • FORM 4 adds open-source distribution, a public CVS repository, extensive documentation, and a user-developer forum.The forum has helped locate bugs and installation problems.
  • The paper surveys FORM's architecture, open-source development, new features, polynomial algorithms, parallel versions, generic facilities, and conclusions.

2 Generic structure

FORM is organized around modular processing of expressions: terms are generated and normalized, then collections are sorted into standard representations. Its architecture combines sequential term processing with disk-based handling of very large expressions and specialized parallel extensions.

  • FORM consists of modules with limited interaction, including normalization and sorting routines plus task-specific and library components.
  • The preprocessor and compiler transform input statements into virtual-machine code stored in compiler buffers.The compiler first creates tokens, performs optimizations, and recognizes identical subexpressions to avoid duplicate storage.
  • The terms generator controls branching during substitutions and expansions, while normalization routines bring terms into normal form.Normalization can also evaluate special functions.
  • The sorting system buffers, sorts, and may write terms to disk, enabling compact representation and relatively fast processing of very large expressions.Large expressions may require disk-to-disk sorting before module output becomes the next module's input.
  • FORM processes terms sequentially, normalizes them after each statement, traverses the expansion tree, and sends completed terms to sorting.
  • Local operations use one term, whereas non-local operations include term comparisons during sorting and factorization of complete expressions.The paper describes constructing inherently non-local operations through combinations of local operations and non-local sorting instructions.

3 Open source and adding new features

FORM 4 is open source under GPL version 3 and is designed so users can extend it with new functions, statements, and $-variable features. Extensions typically connect compiler, generator, and normalization routines.

  • FORM 4 became open source under the GNU General Public License version 3 to allow others to contribute.
  • Adding a function usually requires registering it in header files and implementing its action in normalization routines.Complicated functions may also require routines called from normalization or term generation.
  • Adding a statement requires compiler recognition, virtual-machine code generation, and generator-level execution control.Apart from a few additional lines elsewhere, two routines generally have to be constructed.
  • Extending $-variables follows a similar pattern but requires more work than adding functions.

4 New features

FORM 4.0 extends polynomial handling with factorization across function arguments, expressions, and $-variables, while adding mechanisms for representing, accessing, and preserving factors.

  • 4.1.1 Function arguments: FactArg now factorizes polynomial function arguments into multiple arguments of the same function, extending version 3 behavior beyond single-term factors.The resulting factors are returned as a sequence of arguments, while compatibility support preserves the older behavior.
  • 4.1.1 Function arguments: Function-argument polynomial factorization is limited because both input and combined output polynomials must fit within the maximum term size.
  • 4.1.2 Expressions: Expression factorization stores factors in the bracket system, allowing factorized expressions to be output, directly input, accessed, counted, and later unfactorized.Form keeps factorized expressions in this representation until Unfactorize is used, and NumFactors returns zero for an unfactorized expression.
  • 4.1.2 Expressions: Form supports zero factors during substitutions, retaining a zero factor so that unfactorizing the expression produces zero.
  • 4.1.2 Expressions: Expression factorization uses the single available bracket level, so extra Bracket statements have no effect on factorized expressions.
  • 4.1.3 $-variables: Factorized $-variables retain both unfactorized and factorized copies, with factors accessed by indexed elements and the zeroth element giving the factor count.The factors remain available until the $-variable is redefined; in the example, $X has 4 factors.
  • 4.1.3 $-variables: The $-variable implementation cannot use a triple-dot construction when the factor count is defined only during execution, because triple dots are preprocessor facilities.

4.2 Rational polynomials

FORM 4.0 introduces PolyRatFun for efficient manipulation of rational polynomials, representing fractions through numerator and denominator arguments and normalizing their arithmetic.

  • 4.2 Rational polynomials: PolyRatFun extends the PolyFun mechanism to rational polynomials, which Form combines during sorting when terms are otherwise identical.
  • 4.2 Rational polynomials: PolyFun and PolyRatFun are mutually exclusive declarations, with at most one active at a time.
  • 4.2 Rational polynomials: PolyRatFun interprets two symbol-only arguments as a fraction’s numerator and denominator, supplies denominator one when only one argument is given, and rejects more than two arguments.
  • 4.2 Rational polynomials: The product rat(x,y)*rat(x+1,y+1) is normalized to rat(x^2 + x,y^2 + y).
  • 4.2 Rational polynomials: Fractions are always normalized by dividing the greatest common divisor of numerator and denominator out of both.
  • 4.2 Rational polynomials: A PolyRatFun denominator can be factorized only after converting the rational function to separate numerator and denominator functions, because more than two arguments cause an error.

4.3 ToPolynomial, FromPolynomial and ExtraSymbols

FORM 4.0 adds polynomial-oriented facilities that convert non-symbolic objects into manageable extra symbols and introduces broader transformations for structured argument manipulation.

  • ToPolynomial and ExtraSymbols: ToPolynomial replaces non-symbolic objects with newly defined extra symbols, stores their definitions, and supports later reversal with FromPolynomial.Extra-symbol names avoid conflicts with user-defined names.
  • Polynomial operations: Polynomial support provides user functions for quotient, remainder, gcd, content, and polynomial modular inverse operations.These operations accept polynomial arguments.
  • Do loops: Execution-level Do/EndDo loops use $-variables because preprocessor variables are unavailable during execution.Boundary parameters may be one-word integers or $-variables, including factor indicators.
  • Transform statement: Transform groups operations on large argument ranges, performing complex manipulations internally after simpler matching.This avoids repeatedly passing through the pattern matcher.
  • Transform statement: Transform subkeys include cyclic permutation, arbitrary permutation, encoding, decoding, reversal, harmonic-sum conversion, and Lyndon-word operations.The statement currently supports ten subkeys, ranging from generally applicable to custom-made transformations.
  • Transform statement: A combined transform for Multiple Zeta Values is faster, more readable, easier to program, and less prone to errors than the original repeated operations.The example replaces eight pattern-matcher passes plus a final statement with one transform-based formulation.

4.7 Random and RanPerm

FORM 4.0 adds random-number and random-permutation functions, alongside utilities for extracting leading terms and expressions outside first brackets.

  • Random: Random returns an integer in [1, N] using an additive number generator, with standard initialization unless #SetRandom is used.N must be greater than one.
  • Random: TForm and ParForm workers run separate Random instances initialized differently, so parallel executions may produce different sequences and term assignments.Term distribution across workers is itself non-deterministic.
  • RanPerm: RanPerm generates a random permutation of its remaining arguments and places that permutation in a named output function.The function is useful for testing and debugging programs.
  • Expression utilities: A leading-term function returns the first term of an expression or $-variable, supporting Gaussian elimination and Gröbner-basis programs.FirstBracket instead returns what lies outside the first bracket of a bracketed expression.

4.9 Prime

FORM 4.0 introduces prime-based arithmetic utilities, rational reconstruction, checkpoint recovery, and architecture-independent save files, with explicit resource and compatibility boundaries.

  • Prime arithmetic: MakeRational reconstructs a unique fraction from modular integer results when both numerator and denominator are below the square root of the modulus.This converts calculations performed modulo integers into rational results.
  • Prime arithmetic: Prime generates and caches prime numbers, starting from the largest positive value fitting in one FORM word.On 64-bit computers, the supported range allows O(10^8) prime numbers, but generating all may take a few hours.
  • Prime arithmetic: ExtEuclidean computes modular inverses and supports combining results modulo n1 and n2 into a result modulo n1n2.The method is used with prime-modulus calculations and Chinese-remainder reconstruction.
  • Checkpointing: Checkpointing writes snapshots at module ends according to an optional time interval and allows recovery from the last snapshot after a crash.The -R option invokes recovery, while On Checkpoint and Off Checkpoint control snapshotting.
  • Checkpointing: Checkpoint backups can run external programs before and after writing, including checks for disk space and backup compression or movement.A nonzero or failed pre-write program prevents that module’s data from being written; the post-write program still runs.
  • Save-file portability: Version 4 save files are portable across computer architectures, but old save files are incompatible and 32-bit systems may overflow on larger data.Conversion requires printing old contents as text and loading them into a new save file.

5 Polynomial algorithms

FORM’s polynomial engine uses sparse representations and modular algorithms for addition, multiplication, gcd computation, and factorization, with caching for repeated factorizations.

  • Representation and operations: Polynomials use degree-sparse, variable-dense storage: only nonzero terms are stored, while each monomial retains all variable exponents.This favors sparse-polynomial efficiency while adding some storage overhead.
  • Representation and operations: Polynomial addition and subtraction merge polynomials, while multiplication and division use a binary heap to find successive monomials efficiently.Operations support integers, prime moduli, and prime powers, with prime powers cached for gcd and factorization.
  • GCD algorithms: Univariate gcds use Euclid’s algorithm; multivariate gcds try heuristics before falling back to Zippel’s sparse modular algorithm.The fallback reconstructs multivariate gcds from univariate modular gcds using interpolation and the Chinese remainder algorithm.
  • Factorization algorithms: Univariate modular factorization uses Berlekamp’s algorithm, while integer factorization uses Hensel lifting and combines spurious factors by brute force.Multivariate factorization reduces variables to univariate cases before generalized lifting.
  • Factorization algorithms: A caching mechanism accelerates realistic calculations that factorize the same polynomials repeatedly.

6 Parallel versions

FORM provides two parallel implementations: TForm uses shared-memory threads on one multicore computer, while ParForm distributes work across MPI processes and potentially different computers. Version 4 completes ParForm's facilities so TForm programs can run with it, although communication and parallelization bottlenecks remain.

  • Parallel architectures: TForm uses multiple threads with shared memory, whereas ParForm uses MPI processes that may run across separate computers.Both are intended to behave similarly from the user's perspective, but their data-sharing models differ.
  • Version 4 compatibility: Version 4 fixes ParForm's missing or malfunctioning facilities, enabling TForm programs to run with ParForm.Regular sequential FORM programs should also run with both parallel versions.
  • Trade-offs: TForm minimizes communication and uses several cores, while ParForm offers separate disks that can reduce disk-traffic slowdowns.The trade-off is lower communication for TForm versus potentially less disk contention for ParForm.
  • Limits: Parallel performance eventually plateaus because some FORM operations, including final sorting on the master, cannot be parallelized effectively.The limiting processor count depends on the problem, and the bottleneck remains under development.

7 Facilities

FORM 4 expands its documentation, development infrastructure, and community support while relying on standard libraries for arithmetic, compression, threading, and distributed communication. The release also preserves version 3 program compatibility and supports systematic executable certification.

  • Documentation: The manual is distributed as LaTeX source, PostScript, PDF, and HTML, while remaining a reference manual rather than a tutorial.A future project is to update the older version 2 tutorial to version 4 syntax.
  • Open-source development: New internal documentation and Doxygen-compatible headers make FORM's source code and routines easier to navigate.This documentation was added to make the open-source release more practical for contributors.
  • Certification: A Ruby certification system tests stored FORM examples against their expected output to check whether new executables remain correct.The example collection is intended to grow over time.
  • Community support: A forum supports reports about programs, installation and execution problems, and feature requests from users and developers.Access includes a signup and an anti-spam question.
  • Libraries: FORM uses libgmp, librt, zlib, POSIX threading, MPI, and standard C and C++ libraries; GMP supplies large-integer multiplication, division, and gcd routines.TForm requires the POSIX multithread system, and ParForm requires MPI to build.

8 Conclusions

FORM 4 adds the previously missing factorization facility, broadens its commands and functions, and allows users to implement further additions. The release is supported by open-source infrastructure and community debugging efforts.

  • Conclusions: Factorization, identified as the facility users missed most, is added in FORM version 4.The new capability is presented as a major expansion of FORM's functionality.
  • Conclusions: New commands and functions support future calculations using algorithms substantially different from those used previously.Users can also implement their own additions when the built-in features are insufficient.
  • Conclusions: FORM 4's development is accompanied by contributions from external library authors, funding programs, and users who supplied debugging reports.The acknowledgments specifically credit debugging assistance and comprehensible bug reports.
Loading 1203.6543v1…