Combination of symbolic and numeric methods

The core technology of LGS consists of a combination of symbolic and numerical methods for solving systems of geometric and algebraic constraints.

Variation of constraint graph analysis based on abstract degree-of-freedom approach is one of symbolic methods used in LGS. Strong point of this method is its ability to decompose a complex geometrical problem (with hundreds of constraints) into a sequence of simpler ones. By solving them one by one, LGS provides a solution of the initial problem. Other decomposition algorithms used in LGS are decomposition by biconnected components and pattern-based decomposition of a constraint graph.

The simplest problems obtained after decomposition are solved algebraically; to solve more complex problems numerical methods are applied.

LGS contains powerful processor for numerical solving of algebraic equations. This processor includes some symbolic methods for rewriting of systems of equations; Among them algebraic decomposition method is the most efficient. It performs division of the system of equations into a set of smaller subsystems. Modified Newton method, Newton-Lagrange and gradient methods are numerical methods built in this processor. Newton method is greatly tuned for the class of system of equations generated from geometric specifications. It also applies efficient adaptive strategy of selection of Newton step size.

LGS uses special know-how technique in order to obtain the so called natural solution of geometric problem, i.e. solution that is expected by user. It allows us to avoid using of the homotopy continuation method that is a commonly used routine for finding of natural solutions. On all code levels LGS supports priorities of parameters that allow to obtain the solutions as natural as possible.

Geometric Solver Architecture

Geometric solver has a fine-grained modular architecture based on an internal representation of geometries. The internal representation works with a restricted set of basic geometry primitives (points, lines, curves, etc.) and clusters - product of model decomposition. However, all the needed objects (see Features and benefits) can be easily set in the public API and than translated into the internal representation.

Model decomposition using constraint graph clustering is used to reduce the size of computational models and hence achieve better performance.

During decomposition special cases are diagnosed and processed accordingly: this speeds up computations even more. Most common cases are pre-solved symbolically and then do not require any time to solve.

All constraints and objects are processed immediately after they have been added, and the model is always stored in the internal representation and allows incremental processing. This both reduces computation time, because every time only a part of the design is affected by the change, and also adds interactivity, including fast and accurate inconsistency diagnostics.