Practical simplification of elementary functions using CAD

Abstract

‘Simplification’ is a key concept in computer algebra. But many simplification rules, such as √x√y → √xy, are not universally valid, due to the fact that many elementary functions are multi-valued. Hence a key question is “Is this simplification correct?”, which involves algorithmic analysis of the branch cuts involved. The problem can, in principle, be reduced to connectedness questions and can be solved via Cylindrical Algebraic Decomposition (CAD).

In practice, while CAD is a powerful technique in real algebraic geometry, its application is far from straightforward. This thesis discusses how CAD can be applied to this problem, notably
• initial problem formulation;
• choice of variable ordering;
• problem pre-conditioning;
• decomposition post-conditioning;
for two different CAD algorithms — projection and lifting and triangular decom position.

Date of Award	1 Aug 2011
Original language	English
Awarding Institution	University of Bath
Supervisor	James Davenport (Supervisor) & Russell Bradford (Supervisor)