This volume contains the proceedings of the 2006 Computer Algebra in Scientific Computing (CASC) conference. As well as the contributed papers, it includes the full text of one of the invited talks (Sturm) and the abstract of the other (Watt). I was not able to attend the conference, and am glad to have Sturm’s thoughts, on “new domains for applied quantifier elimination,” preserved.
About half the papers deal with hybrid symbolic-numeric computation, as might be expected. Indeed, these proceedings are an object lesson in showing that the old dichotomy “symbolic or numeric” is dying, if indeed it ever had any real validity. In several cases, the symbolic or numerical parts are distinctly nontrivial: Sobottka and Weber fell across limitations in Maple’s automatic differentiation (successfully circumvented), whereas Grebnicov, Kozak-Skoworodkin, and Diarova ran up against resource limitations for the numerical phase.
Some of the applications are, to say the least, nontraditional. Sobottka and Weber’s work can be applied to the modeling of hair in computer graphics, while Gago-Vargas et al. apply Gröbner bases to the number-placement game Sudoku. Here they note that, while Gröbner bases are theoretically a complete solution, in practice (and I spent several days of computer time before agreeing) they are too costly. They conjecture this is because Gröbner bases are a global approach, whereas human intelligence uses local approaches. As a side result, they prove that the complexity of deciding consistency of a system of quadratics is nondeterministic polynomial time (NP) complete. Ştefănescu produces some new bounds for the real roots of univariate polynomials, and shows again that there is no right answer to this question: a poly-bound approach should be taken. Brown and Gross introduce “efficient pre-processing methods for quantifier elimination,” a topic worthy of future development.
In all, this is a useful record of the state of the art in a variety of applications of computer algebra to diverse questions.