Computer Algebra

The symbolic methods needed for designing analog circuits require mainly solving and simplification of large and often very sparse systems of polynomial equations. Unfortunately, the size of the occurring systems is so large, that most general purpose Computer Algebra systems are unable to handle them. Therefore, we need more powerful, special-purpose systems like Singular.

Singular is a special-purpose Computer Algebra system originally designed for efficient polynomial computations for commutative algebra, algebraic geometry and singularity theory. It features one of the fastest implementations of the Buchberger algorithm which can be used for simplifications and solving of systems of polynomial equations. But even Singular in its current state is only partly up to the needs of symbolic circuit design. New algorithms and implementations are needed which take into account the special nature of the occurring polynomial systems as well as special solution requirements.

More concretely, the following methods are to be examined and implemented in Singular, some of them have already been successfully tested:

Factorizing Buchberger algorithm:

A combination of two advanced Computer Algebra algorithms, Gröbner Basis computation and multivariate polynomial factorization.

Trace algorithm:

The selection strategies during Gröbner basis computations with infinite precision arithmetic are guided by Gröbner basis computations with finite precision (modular computation) arithmetic. This avoids costly (arbitrary precision) integer arithmetic operations and expedites the overall Gröbner Basis computations. Here, fast data exchange via MP is absolutely necessary.

Hybrid (symbolic/numeric) strategies:

Numerically guided symbolic simplification strategies to reduce the number of terms in a system of equations to a moderate size while controlling the numerical error in one or more reference points.

Modular determination of invariants:

Fast modular computational methods are used to determine important invariants like the dimension or multiplicity of the solution set.

Linear algebra methods for nonlinear homogeneous systems:

Methods from linear algebra, in combination with Buchberger's algorithm, are applied to symbolic nonlinear homogeneous equations with the goal to avoid non-sparseness and blow-up's of coefficients in intermediate computations.