TY - GEN

T1 - Global solutions of well-constrained transcendental systems using expression trees and a single solution test

AU - Aizenshtein, Maxim

AU - Barton, Michael

AU - Elber, Gershon

PY - 2010/7/21

Y1 - 2010/7/21

N2 - We present an algorithm which is capable of globally solving a well-constrained transcendental system over some sub-domain , isolating all roots. Such a system consists of n unknowns and n regular functions, where each may contain non-algebraic (transcendental) functions like sin, or log. Every equation is considered as a hyper-surface in and thus a bounding cone of its normal field can be defined over a small enough sub-domain of D. A simple test that checks the mutual configuration of these bounding cones is used that, if satisfied, guarantees at most one zero exists within the given domain. Numerical methods are then used to trace the zero. If the test fails, the domain is subdivided. Every equation is handled as an expression tree, with polynomial functions at the leaves, prescribing the domain. The tree is processed from its leaves, for which simple bounding cones are constructed, to its root, which allows to efficiently build a final bounding cone of the normal field of the whole expression. The algorithm is demonstrated on curve-curve and curve-surface intersection problems.

AB - We present an algorithm which is capable of globally solving a well-constrained transcendental system over some sub-domain , isolating all roots. Such a system consists of n unknowns and n regular functions, where each may contain non-algebraic (transcendental) functions like sin, or log. Every equation is considered as a hyper-surface in and thus a bounding cone of its normal field can be defined over a small enough sub-domain of D. A simple test that checks the mutual configuration of these bounding cones is used that, if satisfied, guarantees at most one zero exists within the given domain. Numerical methods are then used to trace the zero. If the test fails, the domain is subdivided. Every equation is handled as an expression tree, with polynomial functions at the leaves, prescribing the domain. The tree is processed from its leaves, for which simple bounding cones are constructed, to its root, which allows to efficiently build a final bounding cone of the normal field of the whole expression. The algorithm is demonstrated on curve-curve and curve-surface intersection problems.

UR - http://www.scopus.com/inward/record.url?scp=77954655450&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13411-1_1

DO - 10.1007/978-3-642-13411-1_1

M3 - Conference contribution

AN - SCOPUS:77954655450

SN - 3642134106

SN - 9783642134104

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 18

BT - Advances in Geometric Modeling and Processing - 6th International Conference, GMP 2010, Proceedings

T2 - 6th International Conference on Advances in Geometric Modeling and Processing, GMP 2010

Y2 - 16 June 2010 through 18 June 2010

ER -