Factorization: a Geometric Viewpoint
André Galligo: University of Nice-Sophia Antipolis (France)
We briefly present and analyze, from a geometric viewpoint, strategies for designing algorithms to factor bivariate approximate polynomials in C[x,y].
Given a composite polynomial, stably square-free, satisfying a genericity hypothesis (which often appears in the applications) we describe the effect of a perturbation on the roots of its discriminant with respect to one variable, and the perturbation of the corresponding monodromy action on a smooth fiber.
A novel geometric approach, based on guided projection in the parameter space and continuation method above randomly chosen loops, is presented to reconstruct from a perturbed polynomial a nearby composite polynomial and its irreducible factors. An algorithm and its ingredients is described.
His background is in Algebraic geometry and Singularity theory. He then studied Geometry and Computer Algebra, (specially Grobner bases, effective Nullstellensatz, generalized resultants, then factorization of multivariate polynomials), Automatic Differentiation and more recently Approximate algebraic geometry.
He wrote more than 60 research papers, was the adviser of 25 PhD students. He participated to several collaborations with industrial partners (including Elf-Total, EDF, Dassault, Cnes, Essilor, Think3), European projects (Posso, Gaia) and French ANR Gecko. He is a member of the program committee of Mega.
See his web page: http://math1.unice.fr/~galligo/
Symbolic-Numeric Reflections: One
Person's 35-year Perspective
Keith Geddes: University of Waterloo (Canada)
This will be an informal after-dinner talk recalling some events of past years related to scientific computation and computer algebra.
Professor Geddes is one of the two researchers who initiated the University of Waterloo research project, in 1980, which led to the Maple computer algebra system. In 1988 he was a co-founder of Waterloo Maple Inc. and he continues to serve on its Board of Directors. He has served as Scientific Director of ORCCA, the Ontario Research Centre for Computer Algebra based at the University of Western Ontario and the University of Waterloo.
Approximately 50 research publications authored or co-authored by Professor Geddes have appeared in research journals and conference proceedings, on topics related to scientific computation and computer algebra algorithms and systems. He is a co-author of the textbook "Algorithms for Computer Algebra" by Geddes, Czapor and Labahn. He was a major contributor to the foundational algorithms for the Maple computer algebra system.
On Probabilistic Analysis of
Randomization in Hybrid Symbolic-Numeric Algorithms
Erich Kaltofen: North Carolina State University (USA)
Algebraic randomization techniques can been applied to hybrid symbolic-numeric algorithms. Here we consider the problem of interpolating a sparse rational function from noisy values. We develop a new hybrid algorithm based on Zippel's original sparse polynomial interpolation technique. We show experimentally that our algorithm can handle sparse polynomials with large degrees. We also give a (partial) mathematical justification why the Zippel's algebraic randomization technique can be used with our approximate data: the randomly generated non-zero values are expected to be bounded away from zero. We show that the random Fourier-like matrices arising in our algorithm, have the desired rank property in the exact case, and appear usable numerically.
Furthermore, we show that Sylvester matrices of polynomials with nonidentically distributed random coefficients have large condition numbers. That phenomenon has precluded several algebraic randomization techniques from use in the approximate hybrid setting.
This is joint work with Zhengfeng Yang and Lihong Zhi.
Kaltofen's current interests in the symbolic computation discipline are hybrid symbolic/numeric algorithms, efficient algorithms for linear and polynomial algebra, algebraic complexity theory, parallel symbolic computation and generic programming techniques for algorithm implementation. He is a founding member of the LinBox project [http://www.linalg.org].
Kaltofen was the Chair of ACM's Special Interest Group on Symbolic & Algebraic Manipulation 1993 - 95. He serves as associate editor on several journals on symbolic computation. From 1985 - 87 he held an IBM Faculty Development Award. From 1990 - 91 he was an ACM National Lecturer.
He has edited 4 books, including the Computer Algebra Handbook in 2002, published over 130 research articles, and has developed symbolic computation software in Lisp and C++ and contributed to commercial symbolic computation software.
Automating Renormalization of
Quantum Field Theories
Tony Kennedy: University of Edinburgh (UK)
We give an overview of state-of-the-art multi-loop Feynman diagram computations, and explain how we use symbolic manipulation to generate renormalized integrals that are then evaluated numerically. We explain how we automate BPHZ renormalization using "henges" and "sectors", and give a brief description of the symbolic tensor and Dirac gamma-matrix manipulation that is required. We shall compare the use of general computer algebra systems such as Maple with domain-specific languages such as FORM, highlighting in particular memory management issues.Bio:
Tony Kennedy has interests which span theoretical physics, computer science, and mathematics. In theoretical physics he has worked on the perturbative renormalization of quantum field theory, where together with Bill Caswell he constructed a new proof of the fundamental BPH theorem: this proof is now to be found in textbooks on the subject. He also introduced a new algorithm for simplifying Dirac gamma matrix traces using diagrammatic techniques; further work using such methods led to the proof of the negative dimensional isomorphisms of Lie algebras SU(n) = SU(-n) and SO(n) = Sp(-n).
For the past 20 years or so he has worked principally in the area of lattice quantum field theory, which involves using large computers to carry out numerical evaluation of the infinite dimensional integrals that define quantum field theory in the path integral formulation. Here he was one of the authors of the Hybrid Monte Carlo algorithm that made computations that include dynamical fermions feasible. This algorithm is used universally in the field, and is also now a standard Markov Chain Monte Carlo method in many other fields such as neural networks, and appears in many textbooks. Over the past few years he developed the Rational Hybrid Monte Carlo algorithm (in collaboration with his PhD student Mike Clark), which has led to at least an order of magnitude speed up in lattice computations, and has been widely used in the community.
As the computational requirements for lattice field theory are so great he was led to work on developing specialized computers for lattice quantum chromodynamics (QCD), being one of the designers of QCDSP which won the Gordon Bell prize for best price/performance, as well as more recently QCDOC which was the direct precursor of IBM's BlueGene supercomputer.
Among many other activities, he has served on the CFI High Performance Computing Expert Committee several times, been an editor of several leading physics journals, and is on the advisory committee for the annual international lattice field theory conference.
Computing Numerically with
Functions instead of Numbers
Nick Trefethen: Oxford University (UK)
If we make a sequence of computations involving rational numbers, the numerators and denominators tend to grow exponentially in length; floating-point arithmetic contains this growth by pruning to 16 digits at each step. We present an analogous set of ideas, and the "chebfun/ricfun" software system, for computing with piecewise-smooth functions on an interval. Functions are represented by Chebyshev series to approximately 15 digits of precision. Operations such as +, -, x, /, max, min, norm, and zerofinding are carried out fast and accurately within this context, always pruning the accuracy to 15 digits of precision at each step to contain the combinatorial explosion. This is joint work with Zachary Battles and Ricardo Pachon.
As an author he is known for his books Numerical Linear Algebra (SIAM, 1997, with David Bau, III), Spectral Methods in MATLAB (SIAM, 2000), Schwarz-Christoffel Mapping (Cambridge U. Press, 2002, with Tobin Driscoll) and Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators (Princeton, 2005, with Mark Embree); he also won the Catherine Richards Prize for the best article in Mathematics Today in 2000. He has served as editor for many of the leading research journals in numerical analysis, and spent four years as Section Editor in charge of the major review articles in SIAM Review.
As a teacher he has won awards for graduate-level instruction at MIT and at Cornell. An outgrowth of one of his graduate courses at Oxford was the 2002 "SIAM 100-Dollar, 100-Digit Challenge", which became the subject of a 2004 SIAM book by Bornemann, Laurie, Wagon and Waldvogel and its 2006 Springer successor in German.
Trefethen is a Highly Cited Researcher according to www.isihighlycited.com. His approximately 90 publications in research journals span a number of areas within numerical analysis and applied mathematics, including non-normal eigenvalue problems and applications, spectral methods for differential equations, numerical linear algebra, fluid mechanics, computational complex analysis, and approximation theory. He is perhaps best known for developments associated with pseudospectra of non-normal matrices and operators, including theory, algorithms, and applications in fluid mechanics, numerical solution of partial differential equations, numerical linear algebra, shuffling of cards, random matrices, differential equations, lasers, and other fields.
Trefethen was the first winner of the Fox Prize in Numerical Analysis and was a Presidential Young Investigator. During 1998/99 he was the honorary Rouse Ball Lecturer in Applied Mathematics at the University of Cambridge. He received fellowships from the NSF (both graduate and post-doctoral), Hertz Foundation, and IBM. He is a frequent invited speaker at international conferences, including the quadrennial International Congress of Mathematicians (Berlin, 1998) and the International Congress on Applied Mathematics (Hamburg, 1995). Among other committees he has served on the SIAM Council and Board, the Prizes Committee for the London Mathematical Society, and the International Committee for Industrial and Applied Mathematics, and as President of SIAM UK/IE.
Numerical Algebraic Geometry and
Charles Wampler: General Motors (USA)
Numerical algebraic geometry uses numerical methods, principally numerical tracking of paths defined by polynomial homotopies, to find and manipulate algebraic sets defined by systems of polynomial equations. Kinematics is the study of the geometrical aspects of mechanical motion. The kinematical problems arising in the analysis and design of most robots and mechanisms are essentially algebraic, because these devices are well-modeled as rigid bodies in contact along algebraic surfaces. The constraints imposed by the most common types of joints, such as simple hinges or ball-and-socket joints, are equivalent to containments of linear features (points, lines, and planes) that are maintained during rigid body motion of the parts. Kinematical studies have driven the development of numerical algebraic geometry and remain one of its most important application areas. This talk will briefly overview basic numerical algebraic geometry and kinematics.
Numerical Optimization in Hybrid
Lihong Zhi: Chinese Academy of Sciences (China)
Approximate symbolic computation problems such as approximate greatest common divisor(GCD), approximate factorization, and polynomial system solving can be formulated as constrained or unconstrained optimization problems. We exploit the special structure of these optimization problems, and show how to design efficient and stable hybrid symbolic-numeric algorithms based on Gauss-Newton iteration, structured total least squares (STLS), semidefinite programming and other numeric optimization methods.