Invited speakers

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.

Bio:
André GALLIGO is a professor at University of Nice, France and member of the project team Galaad at INRIA, he was born in 1946.

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/

This will be an informal after-dinner talk recalling some events of past years related to scientific computation and computer algebra.

Bio:
Keith Geddes received his Ph.D degree in Computer Science from the University of Toronto in 1973, specializing in Numerical Approximation. He has been a faculty member since 1973 in Computer Science at the University of Waterloo. His research interests lie in the areas of computer algebra systems, algebraic algorithms, and hybrid symbolic-numeric algorithms for scientific computation.

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.

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.

Bio:
Erich Kaltofen received both his M.S. degree in Computer Science in 1979 and his Ph.D. degree in Computer Science in 1982 from Rensselaer Polytechnic Institute. He was an Assistant Professor of Computer Science at the University of Toronto and an Assistant, Associate, and full Professor at Rensselaer Polytechnic Institute. Since 1996 he is a Professor of Mathematics and an Associate Member of Computer Science at North Carolina State University. He has held visiting positions at Tektronix in 1985, the Mathematical Sciences Research Institute in Berkeley in 1985 and 2000, the University of Toronto in 1991, the Ecole Normale Superieure in Lyon in 2005 and the Massachusetts Institute of Technology in 2006.

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.

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.

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.

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.

Bio:
Nick Trefethen is Professor of Numerical Analysis and Head of the Numerical Analysis Group in the Oxford University Computing Laboratory. He was educated at Harvard University (AB 1977, summa cum laude) and Stanford University (MS 1980 and PhD 1982) and has held professorial positions at New York University (Courant Institute), MIT, Cornell University, and Oxford University. He is a Fellow of the Royal Society (London) and a member of the National Academy of Engineering (USA).

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 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.

Bio:
Charles Wampler is a Technical Fellow in the General Motors Research & Development Center, Warren, MI, where his main responsibility is in the area of robotic systems for manufacturing. He has worked extensively on numerical homotopy methods for solving polynomial systems, such as those that arise in robot kinematics. He holds degrees from M.I.T. (B.S., 1979) and Stanford University (M.S., 1980; Ph.D., 1985) in mechanical engineering. He is a Fellow of the ASME and a Senior Member of the IEEE.

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.

Bio:
Lihong Zhi received the B.S. degree in Mathematics from Peking University, Beijing, China, and the Dr.Sci. degree in Computer Algebra from the Institute of Systems Science, Academia Sinica, Beijing, China. From 1998 to 2001, she was an Assistant Professor with the Department of Computer Science, Ehime University, Matsuyama, Japan. From 2001 to 2002, she did post-doctoral research at the Ontario Research Center for Computer Algebra, University of Western Ontario, London, Canada. She is an Associate Professor with the Institute of Systems Science, Academia Sinica.