Web: http://www.ima.umn.edu | Email: ima-staff@ima.umn.edu | Telephone: (612) 624-6066 | Fax: (612) 626-7370
Additional newsletters available at http://www.ima.umn.edu/newsletters

IMA Newsletter #359

September 2006

2006-2007 Program

Applications of Algebraic Geometry

See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.

News and Notes

IMA 2006-2007 Thematic year on Applications of Algebraic Geometry begins

Algebraic geometry has a long and distinguished presence in the history of mathematics that produced both powerful and elegant theorems. In recent years new algorithms have been developed and several old and new methods from algebraic geometry have led to significant and unexpected advances in several diverse areas of application. Motivated by these exciting developments, the year in algebraic geometry and its applications aims to bring together mathematicians, computer scientists, economists, statisticians and engineers from various disciplines in order to enhance interactions, generate new applications and motivate further progress. In the first quarter, the two workshops cover algorithms and software with a particular eye towards applications. In the second and third quarter, the workshops cover applications in optimization, control, statistics, economics and bioinformatics, coding, complexity, communications and computational geometry.

Cheri Shakiban Joins IMA as Associate Director

Professor Cheri Shakiban has joined the Institute for Mathematics and its Applications at the University of Minnesota as associate director for a two-year term. Dr. Shakiban succeeds Debra Lewis, who has completed a two-year term of service at the IMA and returning to the University of California, Santa Cruz, where she is professor of mathematics. A thanks and good-bye to Debra! Cheri Shakiban is a professor of mathematics at the University of St. Thomas in St. Paul, Minnesota, where she served as department chair from 1996 through 2004. Her recent research is mostly in the area of computer vision, in which she studies the detection of symmetries, visual tracking, and the reconstruction of occlusions in space curves, with applications to the description of supercoiled DNA molecules. At St. Thomas she has been very active with the support and mentoring of undergraduate research.

Michigan Tech joins the IMA

Michigan Tech has joined the IMA as a Participating Institution. MTU's representative on the Participating Institutions Council is Mark Gockenbach, interim chair of the Mathematical Sciences Department.

IMA Events

IMA Tutorial

Algebraic Geometric Methods in Engineering

September 15-16, 2006

Organizers: Sanjay Lall (Stanford University), Pablo A. Parrilo (Massachusetts Institute of Technology), Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA))

IMA Annual Program Year Workshop

Algorithms in Algebraic Geometry

September 18-22, 2006

Organizers: Alicia Dickenstein (University of Buenos Aires), Frank-Olaf Schreyer (Universität des Saarlandes), Andrew Sommese (University of Notre Dame)
Schedule

Monday, September 4

All DayLabor Day —IMA closed.

Wednesday, September 6

10:45a-11:45aStart of the Year Reception for IMA visitorsLind Hall 400
11:15a-12:15pStart of the Year Orientation for IMA visitorsLind Hall 409

Thursday, September 7

10:30a-11:00aCoffee BreakLind Hall 400
11:00a-12:00pPostdoc Show and TellEE/CS 3-180
12:15p-1:30pPostdoc Lunch and Posters (RSVP to don@ima.umn.edu until Sep 5)Lind Hall 400
1:30p-2:30pPostdoc Show and Tell (continued)EE/CS 3-180

Friday, September 8

11:15a-12:15pComputer orientation for PostDocs and Longterm visitorsLind Hall 409

Wednesday, September 13

11:15a-12:15pSolving polynomial systems by homotopy continuationAndrew Sommese (University of Notre Dame)Lind Hall 409 AGS

Thursday, September 14

11:15a-12:15pWeekly Tutorial- Real Algebraic GeometryKenneth Driessel (Iowa State University)Lind Hall 409 RAG

Friday, September 15

8:15a-8:45aCoffee and registrationEE/CS 3-176 T9.15-16.06
8:45a-9:00aWelcome and opening remarksDouglas N. Arnold (University of Minnesota Twin Cities)EE/CS 3-180 T9.15-16.06
9:00a-9:50aControl Theory and Algebraic GeometrySanjay Lall (Stanford University)EE/CS 3-180 T9.15-16.06
10:00a-10:30aBreakEE/CS 3-176 T9.15-16.06
10:30a-11:20aSome certified methods for Real Solving - applications in roboticsFabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 T9.15-16.06
11:30a-1:30pLunch T9.15-16.06
1:30p-2:20pControl Theory and Algebraic Geometry (continued)Sanjay Lall (Stanford University)EE/CS 3-180 T9.15-16.06
2:30p-3:00pBreakEE/CS 3-176 T9.15-16.06
3:00p-3:50pSome certified methods for Real Solving - applications in robotics (continued)Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 T9.15-16.06
4:00p-4:30pSecond ChancesEE/CS 3-180 T9.15-16.06

Saturday, September 16

8:50a-9:00aCoffeeEE/CS 3-176 T9.15-16.06
9:00a-9:50aMechanisms and Robot Kinematics: Algebraic FoundationsCharles W. Wampler (General Motors Corporation)EE/CS 3-180 T9.15-16.06
10:00a-10:30aBreakEE/CS 3-176 T9.15-16.06
10:30a-11:20aSolution of Integral and Differential Equations using Algebraic SplinesChandrajit L. Bajaj (University of Texas)EE/CS 3-180 T9.15-16.06
11:30a-1:30pLunch T9.15-16.06
1:30p-2:20pMechanisms and Robot Kinematics: Numerical Algebraic GeometryCharles W. Wampler (General Motors Corporation)EE/CS 3-180 T9.15-16.06
2:30p-3:00pBreakEE/CS 3-176 T9.15-16.06
3:00p-3:50pSolution of Integral and Differential Equations using Algebraic SplinesChandrajit L. Bajaj (University of Texas)EE/CS 3-180 T9.15-16.06
4:00p-4:30pSecond ChancesEE/CS 3-180 T9.15-16.06

Monday, September 18

8:30a-9:15aRegistration and coffeeEE/CS 3-176 W9.18-22.06
9:15a-9:30aWelcome to the IMADouglas N. Arnold (University of Minnesota Twin Cities)EE/CS 3-180 W9.18-22.06
9:30a-10:20aGeneralizing the cross-ratio: the moduli space of n points on the projective line is cut out by simple quadrics if n is not sixRavi Vakil (Stanford University)EE/CS 3-180 W9.18-22.06
10:20a-10:50aCoffeeEE/CS 3-176 W9.18-22.06
10:50a-11:40aFactorization of Sparse PolynomialsTeresa Krick (University of Buenos Aires)EE/CS 3-180 W9.18-22.06
11:40a-1:40pLunch W9.18-22.06
1:40p-2:30pCounting Rational Points on Varieties over Finite FieldsDaqing Wan (University of California)EE/CS 3-180 W9.18-22.06
2:30p-3:00pCoffeeEE/CS 3-176 W9.18-22.06
3:00p-3:50pMaple's Algebraic Curves PackageMark van Hoeij (Florida State University)EE/CS 3-180 W9.18-22.06
4:00p-4:30pSecond Chances, a discussion period to revisit workshop topics and issues and look towards future directions.EE/CS 3-180 W9.18-22.06
4:30p-6:00pReception and Poster Session Lind Hall 400 W9.18-22.06
Computing the Abel map and vector of Riemann constantsBernard Deconinck (University of Washington)
Matt Patterson (University of Washington)
Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite FieldJintai Ding (University of Cincinnati)
Computation of rankings on partial derivativesOleg Golubitsky (Queen's University)
Degenerating ideals to toric ideals: a method used in the solution of a problem from classical invariant theoryBenjamin J. Howard (University of Minnesota Twin Cities)
Approximate radicals for clusters: an approach based on Gaussian elimination or SVDItnuit Janovitz-Freireich (North Carolina State University)
Smooth and Algebraic Invariants of a Group ActionIrina Kogan (North Carolina State University)
Representing NP-Complete problems with polynomials ideals: An exploration of Computational Complexity based on Grobner bases and Hilbert's NullstellensatzSusan Margulies (University of California)
Numerical Campedelli surfaces with algebraic fundamental group of order 9Margarida Mendes Lopes (Universidade Técnica de Lisboa)
Change of order for regular chains in positive dimensionEric Schost (École Polytechnique)
Computing holes in semi-groupsRuriko Yoshida (University of Kentucky)
Irreducible Decomposition of Monomial Ideals and Upper Bound on Number of Irreducible ComponentsMingfu Zhu (Clemson University)
Counting Components Heuristically Hans-Christian von Bothmer (Universität Hannover)

Tuesday, September 19

9:00a-9:30aCoffeeEE/CS 3-176 W9.18-22.06
9:30a-10:20aPolar and dual varieties of real curves and surfacesRagni Piene (University of Oslo)EE/CS 3-180 W9.18-22.06
10:20a-10:50aCoffeeEE/CS 3-176 W9.18-22.06
10:50a-11:40aIntersection and Self-intersection of surfaces by means of Bezoutian matricesLaurent Buse (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W9.18-22.06
11:40a-1:40pLunch W9.18-22.06
1:40p-2:30pProjections methods for the topology of algebraic curves and surfacesBernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W9.18-22.06
2:30p-3:00pCoffeeEE/CS 3-176 W9.18-22.06
3:00p-3:50pApplications of monomial ideals and computational algebra in the reverse engineering of biological networks. Michael E. Stillman (Cornell University)EE/CS 3-180 W9.18-22.06
3:30p-4:30pJunior Colloquium: Peter D. Lax (Ordway Visitor), The Change of Variables Formula for Multiple Integrals Vincent 16
4:00p-4:30pSecond Chances, a discussion period to revisit workshop topics and issues and look towards future directions.EE/CS 3-180 W9.18-22.06
4:30p-4:40pGroup picture W9.18-22.06

Wednesday, September 20

9:00a-9:30aCoffeeEE/CS 3-176 W9.18-22.06
9:30a-10:20aFinding all real solutions contained in a complex algebraic curveCharles W. Wampler (General Motors Corporation)EE/CS 3-180 W9.18-22.06
10:20a-10:50aCoffeeEE/CS 3-176 W9.18-22.06
10:50a-11:40aOn the Effectiveness of Number Theory in Algebraic GeometryJ. Maurice Rojas (Texas A & M University)EE/CS 3-180 W9.18-22.06
11:40a-1:40pLunch W9.18-22.06
1:40p-2:30pTools for extracting information from numerically approximated varieties and schemesChris Peterson (Colorado State University)EE/CS 3-180 W9.18-22.06
2:30p-3:00pCoffeeEE/CS 3-176 W9.18-22.06
3:00p-3:50pThe numerical computation of the multiplicity of a component of an algebraic setDaniel J. Bates (University of Minnesota Twin Cities)EE/CS 3-180 W9.18-22.06
4:00p-4:30pSecond Chances, a discussion period to revisit workshop topics and issues and look towards future directions.EE/CS 3-180

Thursday, September 21

9:00a-9:30aCoffeeEE/CS 3-176 W9.18-22.06
9:30a-10:20aNew Fewnomial Upper Bounds from Gale Dual Polynomial SystemsFrank Sottile (Texas A & M University)EE/CS 3-180 W9.18-22.06
10:20a-10:50aCoffeeEE/CS 3-176 W9.18-22.06
10:50a-11:40aGrobner basis structure and decomposition of polynomial systemsShuhong Gao (Clemson University)EE/CS 3-180 W9.18-22.06
11:40a-1:40pLunch W9.18-22.06
1:40p-2:30pOn the Complexity of Groebner Basis Computation for Regular and Semi-Regular SystemsBruno Salvy (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 W9.18-22.06
2:30p-3:00pCoffeeEE/CS 3-176 W9.18-22.06
3:00p-3:50pMixed Volume ComputationTien-Yien Li (Michigan State University)EE/CS 3-180 W9.18-22.06
3:30p-4:30pColloquium: Peter D. Lax (Ordway visitor), Overview of the Zero Dispersion Limit Vincent 16
4:00p-4:30pSecond Chances, a discussion period to revisit workshop topics and issues and look towards future directions.EE/CS 3-180 W9.18-22.06
6:00p-9:00pWorkshop DinnerKikugawa at River Place W9.18-22.06

Friday, September 22

9:00a-9:30aCoffeeEE/CS 3-176 W9.18-22.06
9:30a-10:20aThe Newton Polytope of the Implicit EquationBernd Sturmfels (University of California)EE/CS 3-180 W9.18-22.06
10:20a-10:50aCoffeeEE/CS 3-176 W9.18-22.06
10:50a-11:40aAlgorithms for Invariant Rings of Algebraic GroupsHarm Derksen (University of Michigan)EE/CS 3-180 W9.18-22.06
11:50a-12:20pSecond Chances, a discussion period to revisit workshop topics and issues and look towards future directions.EE/CS 3-180 W9.18-22.06
12:20p-12:30pClosing DiscussionEE/CS 3-180 W9.18-22.06

Monday, September 25

9:30a-10:30aSemigraphoids, Permutohedra, and MiceBernd Sturmfels (University of California)Lind Hall 305 AGS
11:15a-12:15pAsymptotic Ideal Theory and Parametrized Rational VarietiesDavid Eisenbud (Mathematical Sciences Research Institute)Lind Hall 305 AGS

Tuesday, September 26

11:15a-12:15pApplied Math Seminar: Peter D. Lax (Ordway visitor), Positive schemes for solving hyperbolic equationsVincent 1

Wednesday, September 27

11:15a-12:15pApproximating singular solutions of polynomial systemsAnton Leykin (University of Minnesota Twin Cities)Lind Hall 409 AGS

Friday, September 29

1:25p-2:25pFiber products and exceptional setsCharles W. Wampler (General Motors Corporation)Room 6 Vincent Hall IPS
Abstracts
Colloquium: Peter D. Lax (Ordway visitor), Overview of the Zero Dispersion Limit
Abstract: Many physical theories contain small parameters;thus Schroedinger's equation contains Planck's constant h,the Navier-Stokes equation the reciprocal of the Reynolds number R. The limits h and 1/R tending to zero are of great interest. This talk is about the limiting behavior of solutions of the Korteweg-DeVries equation when the coefficient of dispersion tends to zero.
Chandrajit L. Bajaj (University of Texas) Solution of Integral and Differential Equations using Algebraic Splines
Abstract: This two part tutorial shall introduce you to algorithmic algebraic geometry methods of manipulating algebraic (polynomial) splines necessary for the solution of multivariate integral and partial differential equations emanating from science and engineering applications. In the first part, we shall discuss well known (classical) algorithms for modeling the structure and energetics of physical domains (molecules to airplanes to oil fields), at multiple scales, with implicit algebraic splines (A-patches), and their rational parametric splines (NURBS) approximations. Algebraic geometry methods include computing global and local parameterizations using Newton factorization and Hensel lifting, computation of adjoints by interpolating through singularities, and low degree curve and surface intersections via Resultants and/or Groebner Basis calculations. The second part shall focus on more current research and attempts at using algebraic geometry methods for faster and more accurate calculations of multivariate definite integrals of algebraic functions arising from the solution of polarization energetics and forces (Generalized Born, Poisson Boltzmann) and Green function solutions of two-phase Stokesian flows. These algebraic geometry methods include the use of ideal theory and solutions of polynomial systems of equations for more accurate cubature formulas and their faster evaluation.
Daniel J. Bates (University of Minnesota Twin Cities) The numerical computation of the multiplicity of a component of an algebraic set
Abstract: The solution set of a polynomial system decomposes into a union of irreducible components. The set of polynomials imposes on each component a positive integer known as the multiplicity of the component. This number is of interest not only because of its meaning in applications but also because a number of numerical methods have difficulty in problems where the multiplicity of a component is greater than one. In this talk, I will discuss a numerical algorithm for determining the multiplicity of a component of an algebraic set. This is joint work with Chris Peterson and Andrew Sommese.
Laurent Buse (Institut National de Recherche en Informatique Automatique (INRIA)) Intersection and Self-intersection of surfaces by means of Bezoutian matrices
Abstract: The computation of the intersection and self-intersection loci of parameterized space algebraic surfaces is an important task in Computer Aided Geometric Design. In this talk, we will show that these loci can be represented by particular projections corresponding to certain resultants which can be exactly computed as the determinant of associated Bezoutian-like matrices. This is joint work with M. Elkadi and A. Galligo from the University of Nice.
Bernard Deconinck (University of Washington), Matt Patterson (University of Washington) Computing the Abel map and vector of Riemann constants
Abstract: The Kadomtsev-Petviashvili equation is known to describe approximately the evolution of surface waves in shallow water. This equation admits families of multi-phase solutions parameterised by Riemann surfaces. In order to explicitly calculate these soultions we have created black-box algorithms to compute the Abel map and the Riemann constant vector(RCV). A Riemann surface is associated with its Jacobian through the Abel map. The RCV is the offset between the theta-divisor and the image under the Abel map of the (g-1)-th symetric power of a Riemann surface of genus g. Using a plane algebraic curve representation of the Riemann surface, we provide an algorithm for the numerical computation of the Abel map and the vector of Riemann constants. Since our plane algebraic curves are of arbitrary degree and may have arbitrary singularities, the Abel map and RCV of any connected compact Riemann surface may be obtained in this way.
Harm Derksen (University of Michigan) Algorithms for Invariant Rings of Algebraic Groups
Abstract: Joint work with Gregor Kemper. I will discuss algorithms for finding generators of rings of invariants, with emphasis on reductive groups in positive characteristic and non-reductive groups.
Jintai Ding (University of Cincinnati) Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field
Abstract: We present the Zhuang-Zi algorithm, a new method for solving multivariate polynomial equations over a finite field. The main idea of this new algorithm is the usage of Frobenius map. We will describe the algorithm and present some interesting examples, where this new algorithm works, but other known fast algorithms do not.
Kenneth Driessel (Iowa State University) Weekly Tutorial- Real Algebraic Geometry
Abstract: Dr. Ken Driessel will offer weekly (except for Workshop weeks) tutorial sessions. More details will come. Mark your calendars for now.
David Eisenbud (Mathematical Sciences Research Institute) Asymptotic Ideal Theory and Parametrized Rational Varieties
Abstract: If I is a homogeneous ideal in a polyonomial ring over a field, then in some ways high powers of I are simpler than I itself. This fact is implicitly used whenever one blows up a subvariety of a variety, for example in the process of resolution of singularities. The attendant phenomena appear in commutative algebra in the study of the Rees algebra of a variety. I will explain a new point of view that connects, for example, the parametrization of a rational curve to the singularities of that curve without passing through the "implicitization" step of finding the equations of the image curve. The work I will describe is joint with Joe Harris and Craig Huneke.
Shuhong Gao (Clemson University) Grobner basis structure and decomposition of polynomial systems
Abstract: A Grobner basis for an ideal under an elimination order reflects much of the geometric structure of the variety defined by the ideal. We discuss how this relationship can be used in decomposing polynomial systems (with or without parameters) and in primary decomposition of ideals. As an application, we show how this technique can be used in designing deterministic algorithms for factoring univariate polynomials over finite fields, which aims to reduce the factoring problem to a combinatorial one. The talk is based on joint work with Genhua Guan, Raymond Heindl, Jand-Woo Park, Virginia Rodrigues, and Jeff Stroomer.
Oleg Golubitsky (Queen's University) Computation of rankings on partial derivatives
Abstract: Rankings on partial derivatives generalize admissible term orders and play a similar role: decomposition algorithms for differential algebraic varieties require introduction of a ranking. We propose an algorithm that, given a finite set of differential polynomials with selected leading derivatives, determines whether this selection is consistent with a ranking and, if so, constructs such a ranking. Computation of a universal decomposition of a radical differential ideal, i.e., the one that is valid for any ranking, and the differential generalization of the Groebner walk method rely on the solution of this problem.
Benjamin J. Howard (University of Minnesota Twin Cities) Degenerating ideals to toric ideals: a method used in the solution of a problem from classical invariant theory
Abstract: By weighting monomials appropriately it may be possible to assign a filtration to a ring so that the associated graded ring is toric. If this toric variety is sufficiently simple, one may be able to find the relations among the generators of the toric ideal. Then by lifting these toric relations to the ideal of the original ring, one obtains generators of the original ideal. This method was applied to find a finite generating set of relations among the PGL(2) invariants of n-tuples of points on the projective line. This is joint work with John Millson, Andrew Snowden, and Ravi Vakil.
Itnuit Janovitz-Freireich (North Carolina State University) Approximate radicals for clusters: an approach based on Gaussian elimination or SVD
Abstract: We present a method based on Dickson's lemma to compute the "approximate radical" of a zero dimensional ideal I which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is "global" in the sense that it does not require any local approximation of the zero clusters: it reduces the problem to the computation of the numerical nullspace of the so called "matrix of traces", a matrix computable from the generating polynomials of I. To compute the numerical nullspace of the matrix of traces we propose to use Gauss elimination with pivoting or singular value decomposition. We prove that if I has k distinct zero clusters each of radius at most epsilon in the infinity-norm, then k steps of Gauss elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to epsilon square. We also show that the (k+1)-th singular value of the matrix of traces is proportional to epsilon square. The resulting approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to epsilon square. In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood. This is joint work with Lajos Ronyai and Agnes Szanto.
Irina Kogan (North Carolina State University) Smooth and Algebraic Invariants of a Group Action
Abstract: We provide an algebraic formulation of the moving frame method for constructing local smooth invariants on a manifold under an action of a Lie group. This formulation gives rise to algorithms for constructing rational and replacement invariants. The latter are algebraic over the field of rational invariants and play a role analogous to Cartan's normalized invariants in the smooth theory. The algebraic algorithms can be used for computing fundamental sets of differential invariants. This is a joint work with Evelyne Hubert, INRIA, France.
Teresa Krick (University of Buenos Aires) Factorization of Sparse Polynomials
Abstract: In this talk I will discuss algorithms for factoring polynomials over number fields to reach recent results on sparse polynomials, where the complexity of the algorithm takes into account the fact that the polynomial may have many zero coefficients. For simplicity I'll focus on rational polynomials in one or two variables. The talk will review results by F. Cucker, P. Koiran and S. Smale, 1999, H.J. Lenstra (Jr.), 1999, E. Kaltofen and P. Koiran, 2005 and 2006, and a joint work with M. Avendaño and M. Sombra, 2006.
Sanjay Lall (Stanford University) Control Theory and Algebraic Geometry
Abstract: This talk will discuss how many problems in control theory may be formulated as problems of algebraic geometry. Topics covered include realization theory, homotopy methods for pole placement, construction of Schur functions, stabilization via coprime factorization, systems over rings, controllability, and multidimensional systems. We also discuss more recent research in the area of decentralized control.
Anton Leykin (University of Minnesota Twin Cities) Approximating singular solutions of polynomial systems
Abstract: n the assumption of regularity, the existing tools of numerical algebraic geometry provide an effective way to deal with solution sets of systems of polynomials both 0- and positive-dimensional. Should a solution be singular, Newton's method involved in tracking the corresponding homotopy continuation path loses its quadratic convergence. This talk concerns a symbolic-numerical method called deflation that restores this convergence by considering an augmented system in more variables. Time permitting, we will discuss the higher-order deflation related to the topic of computation of the multiplicities of singular solution components.
Tien-Yien Li (Michigan State University) Mixed Volume Computation
Abstract: Most recent algorithms for calculating the mixed volume of the support A = (A1, ... , An ) of a polynomial system P(x) = ( p1(x), ... , pn(x)) in Cn by first finding all the fine mixed cells in a fine mixed subdivision of A followed by adding the volumes of all those cells will be presented in this talk. The problem of finding all the fine mixed cells, which plays a crucial role when the polyhedral homotopy method is employed to find all the isolated zeros of P(x), is dealt with by solving a series of Phase I problems in Linear Programming.
Susan Margulies (University of California) Representing NP-Complete problems with polynomials ideals: An exploration of Computational Complexity based on Grobner bases and Hilbert's Nullstellensatz
Abstract: We model NP-Complete problems using zero-dimensional polynomial ideals. This encoding adds tools for the understanding of NP-Complete problems based on their algebraic invariants. We have done this for several problems, but for this preliminary report we focus on the graph k-coloring problem. 1) We investigated polynomial ideal models of varying degrees and/or number of variables, and their accompanying Grobner bases. 2) Based on Hilbert's Nullstellsatz, we certify infeasibility. We show that for NP-Complete problems, the smallest degree of the Nullstellensatz certificates must grow. We have designed a large-scale sparse linear algebra heuristic to determine the smallest degree Nullstellensatz certificate, and we have implementated this heuristic in terms of the graph coloring problem and display our experimental results. Joint work with J. De Loera, J. Lee, and S. Onn.
Margarida Mendes Lopes (Universidade Técnica de Lisboa) Numerical Campedelli surfaces with algebraic fundamental group of order 9
Abstract: Joint work with Rita Pardini. The (algebraic) fundamental group of minimal regular surfaces S of general type satisfying c_1^2<1/3 c_2 is now well understood. If it is infinite then the surface has a genus 3 hyperelliptic fibration with at least 4 double fibres. If the algebraic fundamental group is finite then its order is at most 9. Furthermore if the fundamental group has order 9 the surface S is necessarily a Campedelli surface,i.e. a surface with c_1^2=2 and vanishing geometric genus. This poster will present the main ideas of the proof of the bound on the order of finite fundamental groups for such surfaces and also the complete classification of Campedelli surfaces with group of order 9. Some previously unknown examples are found and a very interesting feature is that two of these families provide the first known instance of surfaces with c_1^2>1 having base points for the bicanonical system.
Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) Projections methods for the topology of algebraic curves and surfaces
Abstract: We described algorithms for computing the topology of real algebraic implicit curves and surfaces in dimension 3, based on projections techniques, starting with the algorithm for implicit planar curves. Then we consider curves in dimension 3. Next we describe an algorithm for computing the topology of a general real algebraic surface S. The approach is based on tools from stratification theory and the construction of an explicit Whitney stratification of S. We show how these methods can be turned into effective algorithms, using resultant ans subresultant computations and discussed the problem of iterated resultants and discriminants, for which we give some explicit formula.
Chris Peterson (Colorado State University) Tools for extracting information from numerically approximated varieties and schemes
Abstract: There are natural situations where one is led to consider numeric approximations of varieties, schemes, sheaves, ideals, modules, etc. For instance, given a homogeneous ideal one might be able to determine a reduced primary decomposition via numerical methods (such as homotopy continuation) whereas symbolic methods might be too slow or not even apply. This provides motivation to develop a set of tools to handle and manipulate numerically approximated varieties and schemes. In this talk, I will discuss some tools of use for these objects. This is joint work with Dan Bates and Andrew Sommese.
Ragni Piene (University of Oslo) Polar and dual varieties of real curves and surfaces
Abstract: The theory of polar varieties have been used by Bank et al. and Safey El Din et al. to give algorithms for finding a point on each connected component of a smooth, complete intersection real variety. In this talk, based on ongoing joint work with Heidi Mork, we shall consider possibly singular varieties and study the polar varieties and their relation to the dual variety and to the Gauss map. In particular, we shall look at the case of curves and surfaces.
J. Maurice Rojas (Texas A & M University) On the Effectiveness of Number Theory in Algebraic Geometry
Abstract: One of the most basic notions in polynomial system solving is feasibility: does your system of equations have any roots? We will explore the algorithmic complexity of this problem, focussing on sparse polynomial systems over the real numbers and complex numbers. Over the complex numbers, we will see algorithms completely different from homotopy, resultants, and Grobner bases; and how the Generalized Riemann Hypothesis enters our setting. In particular, we show how earlier methods (of Grigoriev, Karpinski, Odlyzko, and Koiran), depending on unproven number-theoretic hypotheses, can be made unconditional in certain cases. Over the real numbers, we will determine the threshold between polynomial-time and NP-hardness, as a function of the number of variables and monomial terms. In particular, we will give polynomial-time algorithms where only exponential-time algorithms were known before, and we will see how Diophantine approximation enters in an unexpected way. Along the way, we will see how finite fields and p-adic fields are also related to our main focus.
Bruno Salvy (Institut National de Recherche en Informatique Automatique (INRIA)) On the Complexity of Groebner Basis Computation for Regular and Semi-Regular Systems
Abstract: We study the complexity of Groebner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We bound precisely the exponent of the complexity of Faugère F5 algorithm in this case. This complexity is related to the index of regularity of the ideal. For regular systems, this index is well- known. We define a class of overdetermined systems called semi- regular systems for which we derive sharp asymptotic estimates of the index of regularity. These systems are conjectured to be generic in a precise sense. This is joint work with Magali Bardet and Jean-Charles Faugère.
Eric Schost (École Polytechnique) Change of order for regular chains in positive dimension
Abstract: Joint work with Xavier Dahan, Xin Jin, and Marc Moreno Maza. We discuss changing the variable ordering for a regular chain in positive dimension. This quite general question has applications going from implicitization problems to the symbolic resolution of some systems of differential algebraic equations. We propose a modular method, reducing the problem to dimension zero and using Newton-Hensel lifting techniques. The problems raised by the choice of the specialization points, the lack of the (crucial) information of what are the free and algebraic variables for the new ordering, and the efficiency regarding the other methods are discussed. Strong hypotheses (but not unusual) for the initial regular chain are required. Change of ordering in dimension zero is taken as a subroutine.
Andrew Sommese (University of Notre Dame) Solving polynomial systems by homotopy continuation
Abstract: We will give a brief introduction to pathtracking and how it is used to find the solutions of a polynomial system. We will discuss isolated solutions first and, as an extended example of the solution of a nontrivial system, discuss the solution by Charles Wampler and Alexander Morgan (both of GM R & D) and myself of the nine-point path synthesis problem for planar four-bars. As time permits, we will discuss the numerical irreducible decomposition developed by Verschelde, Wampler, and myself.
Frank Sottile (Texas A & M University) New Fewnomial Upper Bounds from Gale Dual Polynomial Systems
Abstract: In 1980, Askold Khovanskii established his fewnomial bound for the number of real solutions to a system of polynomials, thereby showing that the complexity of real solutions to a polynomial system depends upon the number of monomials and not the degree. This fundamental finiteness result in real algebraic geometry was proven by induction on the number of monomials and the bound is unrealistically large. I will report on joint work with Frederic Bihan on a new fewnomial bound which is substantially lower than Khovanskii's bound. This bound is obtained by first reducing a given system to a Gale system, which comes from the Gale dual to the exponent vectors in the original system, and then bounding the number of solutions to a Gale system. Like Khovanskii's bound, this bound is the product of an exponential function and a polynomial in the dimension, with the exponents in both terms depending upon the number of monomials. In our bound, the exponents are smaller than in Khovanskii's.
Michael E. Stillman (Cornell University) Applications of monomial ideals and computational algebra in the reverse engineering of biological networks.
Abstract: he reverse engineering of biological networks is an important and interesting problem. Two examples of such networks are gene regulatory networks, and the relationship of voxels in the brain. We describe a method for determining possible "wiring diagrams" for such networks. The method is based on computational algebra, and a key part of the method uses computations involving monomial ideals in a polynomial ring. To illustrate the algorithms, we apply the method to data coming from fMRI scans of the brain. This talk represents joint work (on the arXiv at q-bio.QM/0605032) with Abdul Jarrah, Reinhard Laubenbacher, and Brandy Stigler. The analysis of the brain data was performed by Paola Vera.
Bernd Sturmfels (University of California) Semigraphoids, Permutohedra, and Mice
Abstract: Semigraphoids are combinatorial structures that arise in statistical learning theory. They are equivalent to convex rank tests and to polyhedral fans that coarsen the reflection arrangement of the symmetric group. This lecture gives an introduction to this theory. It centers around our recent answers to questions raised by Matus, Studeny, Postnikov, Reiner and Williams. This represents joint work with R.Hemmecke, J.Morton, L.Pachter, A.Shiu and O. Wienand. The mice are in the title because everything started with the analysis of microarray data in molecular biology. Reading: Milan Studeny: Probabilistic Conditional Independence Structures, Springer Series in Information Science and Statistics, 2005.
Ravi Vakil (Stanford University) Generalizing the cross-ratio: the moduli space of n points on the projective line is cut out by simple quadrics if n is not six
Abstract: The cross-ratio is a classical gadget that let's you see if two sets of four points on the projective line are projectively equivalent — it is the "moduli space of four points on the projective line." The generalization of this to an arbitrary number of points leads to the notion of the moduli space of n points on the projective line, which is a projective variety, one of the most classical examples of a Geometric Invariant Theory quotient. It also may be interpreted as the space of all polygons in 3-space. We show that this space is actually cut out by quadrics, of a particularly simple sort. This talk is intended for a broad audience. (This is joint work with B. Howard, J. Millson, and A. Snowden, and deals with preprint math.AG/0607372.)
Charles W. Wampler (General Motors Corporation) Finding all real solutions contained in a complex algebraic curve
Abstract: Using the methods of numerical algebraic geometry, one can compute a numerical irreducible decomposition of the solution set of polynomial systems. This decomposition describes the enitre solution set and its breakup into irreducible pieces over complex Euclidean space. However, in engineering or science, it is common that only the real solutions are of interest. A single complex component may contain multiple real components, some possibly having lower dimension in the reals than the dimension of the complex component that contains them. We present an algorithm for finding all real solutions inside the pure-one-dimensional complex solution set of a polynomial system. The algorithm finds a numerical approximation to all isolated real solutions and a description of all real curves in a Morse-like representation consisting of vertices with edges connecting them. The work presented in this talk has been done in collaboration with Ye Lu, Daniel Bates, and Andrew Sommese.
Daqing Wan (University of California) Counting Rational Points on Varieties over Finite Fields
Abstract: In this lecture, we discuss various results on both complexity and algorithms for counting the number of rational points on a hypersurface over a finite field, with am emphasis on p-adic methods.
Ruriko Yoshida (University of Kentucky) Computing holes in semi-groups
Abstract: Does a given system of linear equations with nonnegative constraints have an integer solution? This is a fundamental question in many areas. In statistics this problem arises in data security problems for contingency table data and also is closely related to non-squarefree elements of Markov bases for sampling contingency tables with given marginals. To study a family of systems with no integer solution, we focus on a commutative semigroup generated by a finite subset of \$\Z^d\$ and its saturation. An element in the difference of the semigroup and its saturation is called a "hole." We present an algorithm to compute an explicit description for the difference of a semi-group \$Q\$ generated by vectors in \$\Z^d\$ and its saturation \$Q_{\sat}\$. If \$H=Q_{\sat}\setminus Q\$ is finite, we give an upper bound for the entries of \$h\in H\$. Finally, we present an algorithm to find all \$Q\$-minimal saturation points in \$Q\$. This is joint work with Raymond Hemmecke and Akimichi Takemura.
Mingfu Zhu (Clemson University) Irreducible Decomposition of Monomial Ideals and Upper Bound on Number of Irreducible Components
Abstract: We give three algorithms for finding the irreducible decomposition of monomial ideals. The first one is based on the duality between the intersection and sum operations of monomial ideals. The second one is based on the projection and the staircase structure of monomial ideals. The third one is based on a simple enumeration algorithm to traverse all the facets of the Scarf complex associated with a monomial ideal. Finally, by using The splitting algorithm and the properties of the staircase structure, we give a sharper upper bound on the number of irreducible components . Joint work with Shuhong Gao.
Mark van Hoeij (Florida State University) Maple's Algebraic Curves Package
Abstract: Maple has a number of algorithms for algebraic curves. Algebraic algorithms such as genus, holomorphic differentials, integral basis, parametrization, normal forms for (hyper)-elliptic curves, as well as numeric algorithms such as monodromy and periodmatrix. How these algorithms work is the topic of this talk. Possible future improvements will be discussed as well.
Hans-Christian von Bothmer (Universität Hannover) Counting Components Heuristically
Abstract: Via the Weil-Conjectures one can obtain a lot of geometric information about an algebraic variety X defined over ZZ by counting points over a finite field F_p. Unfortunatedly in many interesting examples it is impossible to count all points because there simply are too many of them. By evaluating the equations of X in a number of random points one can estimate the total number of points with sufficient precision to obtain information about the number of components of X and the codimensions of these components. This method is fast and easily parallelizable, but yields results that are only "probably right."
Visitors in Residence
Jung-Ha An University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Douglas N. Arnold University of Minnesota Twin Cities 7/15/2001 - 8/31/2007
Donald G. Aronson University of Minnesota Twin Cities 9/1/2002 - 8/31/2007
Chandrajit L. Bajaj University of Texas 9/15/2006 - 9/17/2006
Evgeniy Bart University of Minnesota Twin Cities 9/1/2005 - 9/30/2006
Daniel J. Bates University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Sorin Bengea Eaton Corporation 9/15/2006 - 9/16/2006
Gian Mario Besana DePaul University 9/5/2006 - 10/27/2006
Yermal Sujeet Bhat University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Allan Boardman University of Salford 9/30/2006 - 10/4/2006
Francesco Borrelli University of Minnesota Twin Cities 9/15/2006 - 9/16/2006
Laurent Buse Institut National de Recherche en Informatique Automatique (INRIA) 9/17/2006 - 9/22/2006
Eduardo Cattani University of Massachusetts 9/17/2006 - 9/22/2006
Ionut Ciocan-Fontanine University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Maria Angelica Cueto University of Buenos Aires 9/14/2006 - 9/23/2006
Wolfram Decker Universität des Saarlandes 9/1/2006 - 9/30/2006
Bernard Deconinck University of Washington 9/14/2006 - 9/22/2006
Jesus A. De Loera University of California 9/13/2006 - 9/27/2006
Harm Derksen University of Michigan 9/17/2006 - 9/22/2006
Alicia Dickenstein University of Buenos Aires 9/1/2006 - 11/30/2006
Jintai Ding University of Cincinnati 9/17/2006 - 9/24/2006
Sandra Di Rocco Royal Institute of Technology (KTH) 9/1/2006 - 10/20/2006
Xuan Vinh Doan Massachusetts Institute of Technology 9/14/2006 - 9/23/2006
Kenneth Driessel Iowa State University 9/1/2006 - 5/31/2007
David Eisenbud Mathematical Sciences Research Institute 9/23/2006 - 9/29/2006
David Eklund Royal Institute of Technology (KTH) 9/14/2006 - 10/15/2006
Paolo Falcone University of Minnesota Twin Cities 9/15/2006 - 9/16/2006
Makan Fardad University of Minnesota Twin Cities 8/26/2006 - 8/13/2007
Shuhong Gao Clemson University 9/5/2006 - 12/20/2006
Luis Garcia-Puente Texas A & M University 9/17/2006 - 9/22/2006
Sonja Glavaski Honeywell Systems and Research Center 9/15/2006 - 9/16/2006
Oleg Golubitsky Queen's University 9/14/2006 - 9/28/2006
Jason E. Gower University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Genhua Guan Clemson University 9/14/2006 - 9/23/2006
Marshall Hampton University of Minnesota 9/21/2006 - 9/22/2006
Gloria Haro Ortega University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Michael Corin Harrison University of Sydney 9/17/2006 - 9/22/2006
Milena Hering University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Chris Hillar Texas A & M University 9/14/2006 - 9/22/2006
Benjamin J. Howard University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Evelyne Hubert Institut National de Recherche en Informatique Automatique (INRIA) 9/1/2006 - 6/30/2007
Farhad Jafari University of Wyoming 9/1/2006 - 6/30/2007
Itnuit Janovitz-Freireich North Carolina State University 9/14/2006 - 9/23/2006
Noomen Jarboui University of Sfax 9/17/2006 - 9/23/2006
Anders Nedergaard Jensen Aarhus University 9/6/2006 - 6/30/2007
Gabriela Jeronimo University of Buenos Aires 9/4/2006 - 10/31/2006
Roy Joshua Ohio State University 9/17/2006 - 9/23/2006
Mihailo Jovanovic University of Minnesota Twin Cities 9/15/2006 - 9/16/2006
Irina Kogan North Carolina State University 9/14/2006 - 9/20/2006
Martin Kreuzer Universität Dortmund 9/16/2006 - 9/23/2006
Teresa Krick University of Buenos Aires 9/1/2006 - 10/15/2006
Michael Kunte Universität des Saarlandes 9/7/2006 - 9/22/2006
Song-Hwa Kwon University of Minnesota Twin Cities 8/30/2005 - 8/31/2007
Oliver Labs Österreichische Akademie der Wissenschaften 9/14/2006 - 9/23/2006
Sanjay Lall Stanford University 9/14/2006 - 9/22/2006
Niels Lauritzen Aarhus University 8/28/2006 - 6/30/2007
Melvin Leok University of Michigan 9/14/2006 - 9/16/2006
Anton Leykin University of Minnesota Twin Cities 8/16/2006 - 8/15/2007
Tien-Yien Li Michigan State University 9/17/2006 - 9/22/2006
Hstau Liao University of Minnesota Twin Cities 9/2/2005 - 8/31/2007
Tie Luo National Science Foundation 9/17/2006 - 9/20/2006
Laura Lurati University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Gennady Lyubeznik University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Diane Maclagan Rutgers University 9/5/2006 - 11/30/2006
Susan Margulies University of California 9/14/2006 - 9/22/2006
Hannah Markwig University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Thomas Markwig Universität Kaiserslautern 9/1/2006 - 6/30/2007
Guillermo Matera Universidad Nacional de General Sarmiento 9/14/2006 - 9/22/2006
Laura Felicia Matusevich Texas A & M University 9/1/2006 - 11/30/2006
Richard Moeckel University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Nader Motee University of Pennsylvania 9/14/2006 - 9/23/2006
Bernard Mourrain Institut National de Recherche en Informatique Automatique (INRIA) 9/16/2006 - 9/22/2006
Uwe Nagel University of Kentucky 9/1/2006 - 12/1/2006
Uwe Nagel University of Kentucky 9/1/2006 - 9/26/2006
Uwe Nagel University of Kentucky 9/1/2006 - 6/1/2007
Sia Nemat-Nasser University of California, San Diego 9/30/2006 - 10/4/2006
Jiawang Nie University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Xia Ning University of Minnesota Twin Cities 9/15/2006 - 9/16/2006
Michael E. O'Sullivan San Diego State University 9/15/2006 - 10/26/2006
Jang-Woo Park Clemson University 9/17/2006 - 9/23/2006
Pablo A. Parrilo Massachusetts Institute of Technology 9/14/2006 - 9/19/2006
Matt Patterson University of Washington 9/14/2006 - 9/22/2006
Paul Pedersen Los Alamos National Laboratory 9/17/2006 - 9/23/2006
Chris Peterson Colorado State University 9/1/2006 - 12/31/2006
Sonja Petrovic University of Kentucky 9/17/2006 - 9/23/2006
Ragni Piene University of Oslo 9/16/2006 - 9/22/2006
Scott R. Pope North Carolina State University 9/17/2006 - 9/23/2006
Sorin Popescu Stony Brook University 9/1/2006 - 12/31/2006
Kristian Ranestad University of Oslo 9/15/2006 - 9/23/2006
Greg Reid University of Western Ontario 9/6/2006 - 12/1/2006
Victor Reiner University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Joel Roberts University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
J. Maurice Rojas Texas A & M University 9/14/2006 - 9/20/2006
Fabrice Rouillier Institut National de Recherche en Informatique Automatique (INRIA) 9/14/2006 - 9/22/2006
Bjarke Hammersholt Roune Aarhus University 9/12/2006 - 6/30/2007
Olivier Ruatta Université de Limoges 9/17/2006 - 9/28/2006
David Rusin Northern Illinois University 9/1/2006 - 12/31/2006
Michael Sagraloff Max-Planck-Institut für Informatik 9/14/2006 - 9/23/2006
Bruno Salvy Institut National de Recherche en Informatique Automatique (INRIA) 9/17/2006 - 9/22/2006
Arnd Scheel University of Minnesota Twin Cities 7/15/2004 - 8/31/2007
Eric Schost École Polytechnique 9/17/2006 - 9/22/2006
Frank-Olaf Schreyer Universität des Saarlandes 9/5/2006 - 10/15/2006
Pierre Seppecher Université de Toulon et du Var 9/30/2006 - 10/4/2006
Chehrzad Shakiban University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Tanush Shaska Oakland University 9/14/2006 - 9/23/2006
Robert Shore US Air Force Research Laboratory 9/30/2006 - 10/6/2006
Andrew Sommese University of Notre Dame 9/1/2006 - 12/31/2006
Ivan Soprunov Cleveland State University 9/17/2006 - 9/23/2006
Frank Sottile Texas A & M University 9/14/2006 - 9/23/2006
Steven Sperber University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Michael E. Stillman Cornell University 9/18/2006 - 9/29/2006
Bernd Sturmfels University of California 9/19/2006 - 9/26/2006
David Swinarski Columbia University 9/17/2006 - 9/23/2006
Agnes Szanto North Carolina State University 9/14/2006 - 9/22/2006
Nobuki Takayama Kobe University 9/13/2006 - 9/29/2006
Hrishikesh Tamhankar Mississippi State University 9/14/2006 - 9/17/2006
Mina Teicher Bar-Ilan University 9/17/2006 - 9/22/2006
Kathleen Iwancio Thompson North Carolina State University 9/14/2006 - 9/23/2006
Carl Toews University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Igor Tsukerman University of Akron 9/30/2006 - 10/4/2006
Ravi Vakil Stanford University 9/16/2006 - 9/22/2006
Mark van Hoeij Florida State University 9/17/2006 - 9/22/2006
Mauricio Velasco Cornell University 9/17/2006 - 9/22/2006
Jan Verschelde University of Illinois 9/6/2006 - 11/30/2006
John Voight University of Minnesota Twin Cities 8/15/2006 - 8/31/2007
Hans-Christian von Bothmer Universität Hannover 9/17/2006 - 9/23/2006
Charles W. Wampler General Motors Corporation 9/14/2006 - 10/27/2006
Daqing Wan University of California 9/17/2006 - 9/24/2006
Mingsheng Wang Chinese Academy of Sciences 9/15/2006 - 11/15/2006
Oliver Wienand University of California 9/14/2006 - 9/23/2006
Wenyuan Wu University of Western Ontario 9/6/2006 - 12/1/2006
Ihsen Yengui University of Sfax 9/14/2006 - 9/22/2006
Ruriko Yoshida University of Kentucky 9/17/2006 - 9/22/2006
Cornelia Yuen University of Kentucky 9/17/2006 - 9/23/2006
Zhonggang Zeng Northeastern Illinois University 9/18/2006 - 10/27/2006
Hongchao Zhang University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Ji Zhang Purdue University 9/14/2006 - 9/17/2006
Mingfu Zhu Clemson University 9/17/2006 - 9/23/2006
Yan Zhuang University of Illinois 9/1/2006 - 12/1/2006
Legend: Postdoc or Industrial Postdoc Long-term Visitor

IMA Affiliates:
3M, Boeing, Carnegie-Mellon University, Consiglio Nazionale delle Ricerche (CNR), Corning, ExxonMobil, Ford, General Electric, General Motors, Georgia Institute of Technology, Honeywell, IBM, Indiana University, Iowa State University, Johnson & Johnson, Kent State University, Lawrence Livermore National Laboratory, Lockheed Martin, Los Alamos National Laboratory, Medtronic, Michigan State University, Michigan Technological University, Mississippi State University, Motorola, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Rutgers University, Sandia National Laboratories, Schlumberger-Doll, Seoul National University, Siemens, Telcordia, Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois at Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas, University of Wisconsin, University of Wyoming, US Air Force Research Laboratory, Wayne State University, Worcester Polytechnic Institute