Numerical Cylindrical Algebraic Decomposition with Certification via Symbolic Reconstruction (Computer Algebra : Design of Algorithms, Implementations and Applications)

Numerical Cylindrical Algebraic Decomposition

with

Certification

via Symbolic

Reconstruction

穴井 宏和

HIROKAZU ANAI

(

株

) 富士通研究所

/(

独

)

科学技術振興機構

FUJITSU

LABORATORIES

LTD / CREST, JST *

横山

和弘

KAZUHIRO YOKOYAMA

立教大学

/(

独

)

科学技術振興機構

RIKKYO UNIVERSITY /CREST, JST \dagger

Abstract

Recentlyreal quantifier elimination (QE) has been widely used as an effective toolfor solving real algebraic constraints (in particular parametric and non-convex cases) arising in many engineering and industrial problems In fact there are several successful applications of quantifierelimination to practi-calindustrial problems. It is, however, still strongly required todeveloppractically efficient realizations of quantifier elimination. In thispaper we propose a new scheme for efficient cylindrical a\‘igebraic de-composition (CAD) algorithm, which is the most fundamental part of quantifier elimination, based on symbolic-numeric computation.

1

Introduction

Cylindrical algebraicdecomposition(CAD) is a general-purpose symbolicmethodaimingfor quantifier elimination (QE) which is a powerful tool to resolvenon-convex and parametric optimizationproblem $\mathrm{s}$

exactly. However, QE based on

CAD

is not practical

on

real computers, since CAD usually consists of manyof purely symbolic computations and has bad computational complexityin nature.

Against the inherent computationalcomplexityof QEbased on aCAD algorithm, severalresearchers

have focused on QE algorithms specialized to particular types of input formulas,

see

[Wei88, LW93, Wei97 Hon93, GV98]. Thisdirectionis quiteprom ising in practicesincenumber ofimportantproblem $\mathrm{s}$

in engineering have been successfully reduced to the particular input torm ulas and resolved by using

thespecialized QE algorithms. For theconcreteapplications of the scheme,

see

[Wei96, SW97, DSW98, GV96, AHOO,$\mathrm{A}\mathrm{Y}\mathrm{S}\mathrm{H}04_{\mathrm{J}}^{]}$.

However, there still remain manysignificant problems in engineeringthat can not berecast as such

particular formulas. Therefore,it isstrongly desired todevelopanefficient algorithm to realize CAD. One

’anai(Djpfujitsucom

effective way for efficient CAD construction is achievedby utilizing numericalcomputation and derived numerical information onalgebraicnumbers

as

far

as

possible without violatingcorrectnessofthe results

instead of symbolictreatment. So far there

are

several related workstointroduce numericalcomputation into CAD construction [$\mathrm{H}\mathrm{o}\mathrm{n}93\mathrm{b}$, Rat02, AP03]: for example, Ratschanproposedacombinationof

CAD

and interval arithmetic [Rat02], and Anal

&

Parrilo presented improved CAD by using the inform ation ofa numerical feasiblepoint particularly for

convex

optimization [APG3].

Inthispaperwe propose a

new

scheme for an efficient realizationofCADbased

on

symbolic-numeric computation [AY04] , wherenumericalcomputation is used particularlyinhandling algebraicnumbersin the lifting phase ofCADconstruction and we apply “symbolic reconstruction” with

a sm

aller number of

symbolic computations only to the unreliable numerical results to validate them. Our symbolic

recon-struction procedure in the lifting phase is based

on

a dynamic evaluation (DE) technique [Duv94], and

combinedwith successive representationsofalgebraicextensions.

2

Numeric

Computation

with

Symbolic

Reconstruction

Computational difficultyof thelifting phaseofCAD

comes

from

.

Computation

over

Algebraic Extension: For exact computation,

we

have to construct

tow-ers of algebraic extension fields successively

over

the rational number field Q. This requires heavy computationssuch

as

algebraicfactorization, GCD of polynomials.

.

CombinatorialExplosion:

CAD

decomposesthe whole

space

$\mathbb{R}^{n}$into

numerous

sub-algebraicsets.

The computational flow ofthe decomposition

can

be illustrated bya computational tree. However, in $\mathrm{Q}\mathrm{E}$,manysuchsub algebraicsets

are

unnecessary, and manysubtree should bediscarded.

Toresolvethesedifficulties

we

considerusing floatingpointsnumberinCAD construction. In contrast to symbolic construction of CAD, replacing every symbolic computation (except projection phase in

CAD construction) with its approximate numerical computation,

we can

compute an numerical CAD

(i.e. approximate CAD) quite efficientlydue toavoidanceofcomputation

over

algebraic extension.

2.1

Using

numerical

computation

in

CAD

Usingnumerical computationin handling algebraicnumbers greatly improvesthe efficiency of CAD

construction because

we can

avoidsymboliccomputationsover algebraic extensionfields and also prune

unnecessary branches of a CAD tree by numerical values of algebraic numbers,while this

causes

uncer-tainty of the computed results depending

on

accuracy ofnumericalcomputation. Hencewe proposeto

use

numericalcomputationwithmachineryforvalidatingnumerically computedresultsby reconstructing them exactlywith asmaller number ofsymbolic computations. Some possible computationalflow of

our

schem $\mathrm{e}$inthe lifting phaseisillustrated inFig.1. Thedotted

arrows

and solid

arrows

in Fig.l stand for numericalcomputationandsymbolic reconstruction, respectively.

Actually computations

over

algebraic extension fields

are

required in the lifting phase ofCAD to computerespectiveisolatinginterval of algebraicnumbers

over

successiveextensionfields. Then what

we

need todo is “sign determination” ofmany algebraic numbers, i.e., to determine exactlywhether they

reconstruction

$\mathrm{v}\mathrm{e}\mathrm{r}\hat{|}\mathrm{f}\hat{\iota}\mathrm{c}\mathrm{a}\mathrm{t}:’ \mathrm{o}\mathrm{n}\mathrm{a}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{E}\hat{;}0’$

:

Figure1:

CAD

construction- numerical computation with symbolicreconstruction

done byonlynumericalcomputation. Wecheck againthe sign exactly by symbolic computation only for

unreliable numerical results (We callthis symbolic reconstruction,) This isthe ground why

our

method would improve theefficiencyofCAD construction.

2.2

Efficient

symbolic

reconstruction

by

using

a

numerical CAD

Moreover we improve the reconstruction procedure by employing a dynamic evaluation technique integrated with successiverepresentationsof algebraicextensions as follows: Algebraic extension is

ex-pressedbya residueclassring$Q[X]/A\mathit{4}$,where$X$isa setofvariables and$M$isa maximal idealin$Q[X]$.

Usually, computation of maximal ideals tends to be very hard. Instead of $\mathbb{Q}[X]/.\Lambda 4$,

we

utilize “lazy

representation” $\mathbb{Q}[X]/J$, where$J$is notnecessary maximalbut easily computable. $\mathbb{Q}[X]/J$maynotbe

a

domain, i.e., it couldhave

zero

divisors. In the computation

over

$\mathbb{Q}[X]/J$, ifagivenalgebraic number

does not correspond to azero-divisor,then it is not equalto 0 and we check its sign by usinga certain

numerical method. Ifwemet

some zero

divisors$ab=0$, the we

can

split the ideal Ias follows:

$J$$=$ $(J +\langle a\rangle)\cap(J +\langle b\rangle)$.

This decomposition is achieved by $\mathrm{g}\mathrm{c}\mathrm{d}$computation for univariatecase, i.e. simple algebraicextension,

and Grobner basis computation for multivariate

case.

Thus, by using lazy representation successively for towersofextensions,where defining polynomials for algebraicnumbers are used as generators of the

ideal $J$,

we

do not requireany algebraicfactorization and

a

primitiveelement computationfor

a

simple

extension which

are

often difficult especially in the

case

oftall towers of extensions. Furthermore the most crucial point is that

we

can

easily choose

one

necessary branch $J$$+\langle a\rangle$ in the decomposition by

virtueofnumericalinformation ofalgebraicnumbers and hence

can prune

unnecessary branches for the

3

Concluding

Remarks

Wepresenta newscheme forrealizingefficient CAD based

on

symbolic-numeric computation. Inorder to

exa

mine its effectiveness, implementation ofour schem $\mathrm{e}$into SyNRAC, which is

a

maple package for

solving real algebraicconstraintsdevelopedat FUJITSULABORATORIESLTD [YA04],isongoing. We

rem

ark that this work also providesoneof prom ising directions for validated numerics for optimization problems.

Acknowledgements :This work has been partially supported by CREST, JST (Japan Science and TechnologyAgency).

References

[AHOO] H.Anai andS. Hara. Fixed-structure robustcontrollersynthesisbasedonsigndefinite condi-tion byaspecialquantifier elimination. In Proceedings

_of

American Control

_Conference

2000, pages 1312-1316, 2000.

[AP03] H. Anai and P. A. Parrilo. Convex quantifier elimination for semidefinte programming. In Proceedings

_of

the 6th International Workshop

on

Computer Algebra in

_Scientific

Computing

2003. To appear, 2003.

[AY04I H. Anai and K. Yokoyama. Numerical cylindrical algebraic decompositionwith certificated reconstruction. InProceedings

_of

11th GAMM-$IMACS$InternationalSymposium

on

Scientific

Computing, ComputerArithmetic, and Validated Numerics (Fukuoka, Japan), page 31, 2004.

[AYSH04] H. Anai, H.Yanami, K.Sakabe, andS. Hara. Fixed-structurerobustcontrollersynthesisbased

onsymbolic-numeric computation: design algorithms with

a

CACSDtoolbox(invited paper). In Proceedings

_of

$CCA/ISIC/CACSD$

₂₀₀₄

(Taipei, Taiwan), pages1540-1545 2004.

[DSW98] A. Dolzmann, T. Sturm, and V. Weispfenning. Real quantifier elimination in practice. In B. H. Matzat, G.-M. Greuel, and G. Hiss, editors, Algorithmic Algebra and Number Theory,

pages 221-247. Springer, Berlin, 1998.

[Duv94] D. DuvaL Algebraic numbers: anexampleof dynamic evaluation. Journal

of

Symbolic Com-putattion, 18:429-445, 1994.

[GV96] L. Gonzalez-Vega. Applying quantifier elimination to the Birkhoff interpolation problem. Journal

_of

Symbolic Computation, 1996. To appear,

[GV98] L. Gonzalez-Vega. A combinatorial algorithm solving

some

quantifier elimination problems. In$\mathrm{B}.\mathrm{F}$. Caviness and $\mathrm{J}.\mathrm{R}$. Johnson, editors, QuantifierElimination and Cylindrical Algebraic

Decomposition, Texts and Monographs in Symbolic Computation, pages 365-375. Springer, Wien, NewYork, 1998.

[Hon93] H. Hong. Quantifier elimination for formulas constrainedby quadratic equations. In Manuel

Bronstein,editor, Proceedings

_of

theInternationalSymposiumonSymbolicand Algebraic Com-putation (ISSAC 93), pages264-274, Kiev, Ukraine, July 1993. ACM, ACM Press.

$[\mathrm{H}\mathrm{o}\mathrm{n}93\mathrm{b}]$ H.Hong. Efficient method foranalyzing topologyofplane real algebraic

curves.

In Proceedings

[LW93] R. Loos and V. Weispfenning. Applying linear quantifier elim ination. The $Comp’\prime xter$ Journal,

36(5):450-462, 1993. Special issueon computational quantifier elimination.

[Rat02] S. Ratschan. Approximate quantified constraint solving by cylindrical box decomposition.

Reliable Computing, 8(1)$:21-42$, 2002.

[SW97] T.Sturmand V. Weispfenning. Rounding and blending ofsolidsbyarealeliminationmethod. In Achim Sydow,editor, Proceedings

_of

the 15th IMACS World Congress

on

Scientific

Com-putation, Modeling, and AppliedMathematics (IMACS 97), volume 2, pages 727-732, Berlin, August 1997. IM ACS, Wissenschaft

&

Technik Verlag.

[Wei88] V. Weispfenning. The complexityoflinear problem $\mathrm{s}$ in fields. Joumat

of

Symbolic

Computa-tion, 5(1-2):3-27, February-April 1988.

[Wei96] V. Weispfenning. Applying quantifier elim ination to problems insimulation andoptimization.

TechnicalReport MIP-9607,FMI, UniversitatPassau, D-94030Passau, Germany, April 1996.

To appearinthe JournalofSymbolic Computation.

[Wei97] V.Weispfenning. Quantifierelim ination for real algebra–thequadraticcase andbeyond. Ap-plicable Algebrain Enginee$\mathit{7}\mathrm{z}ng$ Communication and Computing, $8(2):85-101$, February 1997,

[YA04] H. Yanami and H.Anai. Development of$\mathrm{S}\mathrm{y}\mathrm{N}$RAC- formuladescriptionand newfunctions. In

Proceedings

_of

International Workshop on Computer Algebra Systems and their Applications (CASA)

_2004:

ICCS2004, LNCS3039, pages 286-294.Springer, 2004