UIUC Dept. of Mathematics Seminar Calendar

    December 2004           January 2005          February 2005    
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
           1  2  3  4                      1          1  2  3  4  5
  5  6  7  8  9 10 11    2  3  4  5  6  7  8    6  7  8  9 10 11 12
 12 13 14 15 16 17 18    9 10 11 12 13 14 15   13 14 15 16 17 18 19
 19 20 21 22 23 24 25   16 17 18 19 20 21 22   20 21 22 23 24 25 26
 26 27 28 29 30 31      23 24 25 26 27 28 29   27 28               
                        30 31

Monday, February 14, 2005

Applied/Interdisciplinary Mathematics seminar
3:00 pm in 100H Talbot, Monday, February 14, 2005

Del

Edit

Copy

Submitted by vzh.

Jared Bronski (UIUC Math)
The modulational instability for periodic standing waves
Abstract: Abstract: We consider the (linearized) stability of a standing wave solution to the nonlinear Schrodinger equation with a periodic potential. We give a general condition (non-perturbative) which guarantees the existence of a modulational instability. In the case of weak nonlinearity this instability has a nice interpretation in terms of the "effective mass" of a particle in the periodic potential. This is joint work with Zoi Rapti.

Monday, March 7, 2005

Monday, March 14, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 100H Talbot, Monday, March 14, 2005

Del

Edit

Copy

Submitted by r-sowers.

Eric Brown [email] (New York University)
Modeling optimal decisions with neural integrators and oscillators
Abstract: This talk covers models of neural dynamics at two different scales: abstracted neural “integrators,” which represent competing neural subpopulations involved in simple decision tasks, and smaller-scale models of neural oscillators, which are believed to control and optimize these integrator networks. Via a phase reduction and probability density formulation, neural oscillators are used to model distinct brainstem firing patterns that have been linked with distinct levels of performance in simple cognitive tasks. A possible role for these firing patterns in optimizing speed and accuracy in decision tasks is then studied via stochastic differential equations for neural integrators. This joint work with Jeff Moehlis, Phil Holmes, Mark Gilzenrat, and Jonathan Cohen.

Monday, March 28, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 100h Talbot, Monday, March 28, 2005

Del

Edit

Copy

Submitted by bronski.

Kirsten Boyd (Eureka College)
Subgrid Upscaling and Mixed Multiscale Finite Element Methods
Abstract: The mixed finite element approximation of the Darcy flow problem in porous media has been placed in an abstract subgrid upscaling framework by T. Arbogast, and T. Hou et al. have developed a specific multiscale finite element method (MsFEM) for this problem. In this talk,connections between subgrid upscaling and MsFEM will be explored,elucidating the error estimates obtained by Z. Chen and T. Hou. The work presented is in collaboration with Todd Arbogast of the University of Texas at Austin.

Monday, April 4, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 110h Talbot Hall, Monday, April 4, 2005

Del

Edit

Copy

Submitted by bronski.

David J. Muraki (Simon Fraser University)
Waves Generated by Airflow over a Mountain Ridge
Abstract: When density stratified air is forced over elevated terrain the vertical displacement results in a pattern of dispersing waves. Such vertical disturbances are important in the understanding of microscale variations in precipitation patterns for alpine communities (ski resorts) In a special case R. Long (1953) observed that the steady nonlinear streamfunction satisfies the linear helmholts equation. Two solution methods via integral equations are presented, one of which greatly extends the parameter range over which solutions can be computed. We have recently discovered that these steady solutions are susceptible to instability via a triad resonance mechanism. This opens to question estimates of atmospheric wave turbulence based on steady state assumptions.

Monday, April 18, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 100h Talbot , Monday, April 18, 2005

Del

Edit

Copy

Submitted by bronski.

Mary Pugh (University of Toronto)
"Blowing-up exact solutions of long-wave unstable thin film equations"
Abstract: Long-wave unstable thin film equations $$h_t = (h^n h_{xxx})_x - B (h^m h_x)_x $$ are a fourth-order analogue of the the semilinear heat equation. A "reaction" term destabilizes a "diffusion" term, allowing for a competition between effects. This competition admits a variety of steady states and temporal behaviors, depending on whether the equation is subcritical, critical, or supercritical. In the critical case, Witelski, Bertozzi, and Bernoff propose a critical mass, $M_c$, and demonstrate that if the mass of the initial data is less than $M_c$ then finite-time blow-up is impossible. Their computations and asymptotics case suggest that (generically) if the initial mass is larger than $M_c$ the resulting solution demonstrates selfsimilar blowup focussed at points. Slepcev and I consider the critical case and construct exact solutions with compact support that blow up in a selfsimilar manner. Their mass can be arbitrarily close to the critical mass proposed by Witelski et al., proving the sharpness of the critical mass. In addition, Slepcev has proven the linear stability/instability of such solutions.

Monday, April 25, 2005

Monday, September 12, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, September 12, 2005

Del

Edit

Copy

Submitted by r-sowers.

Vinayak Shanbhag (Dept. of Mechanical and Industrial Engineering, UIUC)
Equilibrium Programming under Uncertainty
Abstract: We consider three equilibrium problems in which agents solve continuous stochastic nonlinear programs. The problems differ in the structure of the agent problem. In each instance, we provide a sampling-based method for obtaining an equilibrium point. Convergence theory and computational results are also provided. We construct a two-period spot-forward market under uncertainty. Such games may be formulated using a Nash-Stackelberg framework resulting in a Nash Stackelberg equilibrium (NSE). However, both determining the existence and obtaining such equilibria is difficult. Instead, we propose a simultaneous stochastic Nash game which requires the solution of a stochastic complementarity problem. We present a sampling-based iterative-decomposition method for solving such problems efficiently and prove its convergence. Some computational experience on a 6-node electricity market is also provided. We consider a class of stochastic convex quadratic programs (QPs). A motivation for studying this class of problems is provided through an example of stochastic Nash games. We extend earlier work in interior sampling methods to allow for sampled inexact cuts. By ensuring that the sampled cuts stay probabilistically valid, we may extend the result to the sampled inexact cuts. The performance of this algorithm is demonstrated for a suite of two-stage stochastic programming test problems. Interior point methods for mathematical programs with complementarity constraints (MPCC) were first proposed by Luo \etal in their monograph. We consider the generalization of the MPCC to the two-stage case under uncertainty and term the resulting problem as a stochastic MPCC. A new primal-dual method is suggested for such a class of ill-posed stochastic nonlinear programs. The method relies on using sampling to construct the linearized KKT system which is subsequently solved using a scenario-based decomposition. Convergence theory and some computational results from a test set of stochastic MPCCs are also provided.

Monday, September 19, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, September 19, 2005

Del

Edit

Copy

Submitted by r-sowers.

P. S. Krishnaprasad [email] (Dept. of Electrical Engineering, University of Maryland at College Park)
Natural Frames, Interacting Particles and Stealth
Abstract: R. L. Bishop pointed out that there is a natural way to frame a curve. The associated frame equations, analogous to the Frenet-Serret equations, can be viewed as a control system on a Lie group, with natural curvatures as controls. In this talk we show how certain feedback laws specifying interaction of two or more curves via their curvatures produce coherent patterns of movement of systems of particles. We then proceed to show that in contrast to such a cooperative setting, one can also consider situations of conflict (e.g. predator-prey interactions, territorial combat, in biological settings). Novel interaction laws for these settings appear to capture some observed spatial patterns in nature associated to stealth strategies.

Monday, September 26, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, September 26, 2005

Del

Edit

Copy

Submitted by r-sowers.

Chris Jones [email] (University of North Carolina, Chapel Hill)
Lagrangian dynamics in the ocean: its assimilation and assessment
Abstract: Much of the data for the ocean is Lagrangian in that it is derived from subsurface floats drifting with the flow. At the same time, many questions about the ocean involve transport and mixing, and therefore concern Lagrangian dynamics. A strategy for model analysis, based on dynamical systems ideas, at both model input and output will be described. This will include Lagrangian data assimilation, optimal float placement design and an approach to model evaluation.

Monday, October 3, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, October 3, 2005

Del

Edit

Copy

Submitted by r-sowers.

Wendy Zhang [email] (University of Chicago)
Liquid interfaces in viscous straining flows:numerical studies of the selective withdrawal transition
Abstract: In selective withdrawal, the interface between two liquid layers is deformed by an imposed withdrawal flow. A shape transition occurs when the flow rate exceeds a threshold value. This changes the topology of the interface from a steady-state hump to an entrained spout. Previous measurements [Cohen \& Nagel Phys. Rev. Lett. 2002] suggest the sharp hump is created via an approach towards a steady-state singular shape which is cut off at a small length-scale. Here we present a numerical model of selective withdrawal. Our results are consistent with previous measurements. However, the increased resolution in the simulation enables us to identify the shape transition as a saddle-node bifurcation and to clarify the shape evolution near the singularity: the transition does not involve approach towards a singular shape. Remarkably, results at threshold subjected different reservoir conditions collapse when appropriately rescaled. (Work with Marko Kleine Berkenbusch. Acknowledgement: We thank Sidney R. Nagel and Itai Cohen forhelpful discussions.)

Monday, October 10, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, October 10, 2005

Del

Edit

Copy

Submitted by r-sowers.

Igor Mezic [email] (Dept. of Mechanical Engineering, UC Santa Barbara)
Control of Mixing: Ergodic Theory and Biosensors
Abstract: The subject of fluid mixing has received substantial attention in the applied mathematics community in the last 20 years, due to its close connections with chaos theory in dynamical systems. Initially, the subject was treated using geometric dynamical systems techniques and the associated concepts of stable and unstable manifold intersection that leads to chaos on a localized subset of the physical space. The same notions, when extended to render global results lead early in this century to Hopf's proofs that certain dynamical systems are ergodic. But, the perspective of ergodic theory on mixing is different, and much closer to the classical engineering perspective, where the mixedness is probed globally (over the whole physical space the fluid is contained in). Unfortunately, the techniques required for proving that a dynamical system is mixing are typically hard. Additionally, engineers would like to control mixing, not just analyze it - although a typical practicing engineer will deem mixing a relatively easy problem: turbulence will get it done. Enter modern biosensors: microfluidic devices that typicaly have laminar flow due to low Reynolds number but require good mixing. Not so easy to mix anymore. 100's of publications a year on the topic... We will describe a framework for feedback control of mixing that allows for treatment of the advective mixing problem. In order to arrive there, we will question variance of the mixture as a good measure in the case of high Peclet, low Reynolds number. Experiments on open loop mixing in an active microfluidic device will be shown. A new norm, named mix-norm is developed and proven equivalent to a negative Sobolev space norm. This object, measuring weak convergence to uniformity, allows for interesting short proofs of mixing in some well-known maps and also for numerical methods to check mixing in dynamical systems. The control of mixing problem is then studied from the perspective of optimal control. We will conclude with some remarks on using these techniques in other problems that require control to chaos instead of control to stability.

Monday, October 17, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, October 17, 2005

Del

Edit

Copy

Submitted by r-sowers.

Kaushik Bhattacharya [email] (Dept. of Mechanical Engineering, CalTech)
Variational problems without solution and microstructure of materials
Abstract: Active materials like shape-memory alloys form fine-scale microstructure. Further, the microstructure can change in response to applied loads, and this evolution is responsible for the unusual properties of these materials. It is possible to model these materials using a continuum theory of thermoelasticity, wherein the equilibrium states are determined by minimizers of the total energy. However, the energy density has multiple wells, each corresponding to different a different phase, and the problem of energy minimization often fails to have any (classical) solution. Instead, minimizing sequences develop oscillations which are interpreted as fine scale microstructure. This talk will describe the modeling and analysis of these materials.

Monday, October 24, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, October 24, 2005

Del

Edit

Copy

Submitted by r-sowers.

Alex Powell (Vanderbilt University)
Sigma-Delta modulation and finite frames
Abstract: Redundancy is a key to practical and reliable data representation in many settings. Frame theory provides a mathematical framework for stably representing signals as linear combinations of an overcomplete collection of "basic building blocks." We shall discuss the problem of quantization (analog-to-digital signal conversion) for redundant finite frame expansions. Our focus will be on a special class of algorithms, known as Sigma-Delta schemes, which are related to error diffusion. We explain the basics of how Sigma-Delta schemes work in this setting, and point to directions of current and future research (including stability theorems and error estimates).

Monday, October 31, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, October 31, 2005

Del

Edit

Copy

Submitted by r-sowers.

Harry Dankowicz [email] (Dept. of Mechanical and Industrial Engineering, UIUC)
Near-Grazing Dynamics in Tapping-Mode Atomic Force Microscopy
Abstract: > Nanostructured materials and devices can be endowed with novel physical properties that make them suitable for a wide range of applications. Carbon nanostructures exhibit hydrogen-adsorbing characteristics that make them attractive candidates as storage devices in a hydrogen-fuel supply chain. Similarly, self-assembly of ferromagnetic nanoparticles is a promising technique for producing high-density magnetic data storage devices and biomedical materials with desirable surface properties. > > Characterization techniques of carbon nanotubes through electron microscopy are tedious and destroy the sample integrity. Similarly, as many of the structures resulting from self assembly of nanoparticles are soft and fragile, their topography can be damaged by the use of conventional nanoscale materials characterization instrumentation. > > Less destructive characterization is possible using scanning-probe microscopy, e.g., intermittent-contact (TappingModeTM) atomic-force microscopy. Here, however, nonlinear effects due to large variations in the force field on the probe tip over very small length scales and the intermittency of contact may induce strong dynamical instabilities. These can result in a sudden loss of stability of low-contact-velocity oscillations of the atomic-force-microscope tip in favor of oscillations with high contact velocity and destructive, nonrepeatable, and unreliable characterization of the nanostructure. > > In tapping-mode microscopy, the onset of instability can be traced to a critical choice of values for system parameters, for which a periodic trajectory exists that achieves zero-normal-velocity (grazing) contact with a system discontinuity. Dynamical-systems methods for the analysis of mechanical and physical systems with intermittent contact can be employed to formulate normal-form descriptions of the near-grazing dynamics that capture the destabilizing effects of contact (cf. [1, 2], but see also [3]). In particular, near-grazing dynamics can be analyzed through the introduction of a discontinuity mapping that i) captures the local dynamics in the vicinity of the grazing contact including variations in time-of-flight to the discontinuity and the contact behavior; ii) can be entirely characterized by conditions at the grazing contact; iii) is nonsmooth in the deviation from the point of grazing contact; and iv) can be studied to arbitrary order of accuracy. > > In this talk, a discontinuity-mapping analysis is employed to investigate the near-grazing dynamics in a lumped-mass model of an oscillating atomic-force-microscope cantilever tip interacting with a sample surface. Here, surface interactions are modeled through a combination of the attraction due to van-der-Waals forces and the repulsion due to Pauli and ionic exclusion. Two different normal forms are derived that capture the critical transition between non-contact oscillations that experience only surface attraction and intermittent-contact oscillations that also experience the repelling response of the sample. The analysis predicts the loss of stability associated with near-grazing contact and suggests ways to suppress such loss through passive redesign and active control. > 1. Dankowicz, H. and Nordmark, A.B., "On the origin and bifurcations of stick-slip oscillations," Physica D 136(3-4), pp. 280-302, 2000. > 2. di Bernardo, M., Budd, C.J., and Champneys, A.R., "Normal form maps for grazing bifurcations in n-dimensional piecewise-smooth dynamical systems," Physica D 160(3-4), pp. 222-254, 2001. > 3. van de Water, W. and Molenaar, J., "Dynamics of vibrating atomic force microscopy," Nanotechnology, 11, pp. 192-199, 2000.

Monday, November 7, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, November 7, 2005

Del

Edit

Copy

Submitted by r-sowers.

Marc Garbey [email] (Department of Computer Science, University of Houston)
A Domain Decomposition method to compute PDEs on the grid
Abstract: Nowadays standard processors are becoming multi-cores and there is a strong incentive to make use of all these parallel resources while avoiding conflict in memory access. We have also an overwhelming abundance of parallel computers available with the grid. Modern numerical solver such as Krylov methods or Multigrid technique are sensitive to memory cache, high latency network and low bandwidth. The computation of a scalar product or the solution process on the coarse grid introduces a strong bottleneck in the execution time. We will present in this talk a new family of domain decomposition solver that works efficiency in grid computing and is competitive with today fast solvers. Our method is based on the acceleration of the traces generated by any blockwise relaxation scheme such as the additive Schwarz method. This postprocessing algorithm can be added easily to an existing code. We will illustrate our method on elliptic and parabolic solver for CFD problems.

Monday, November 14, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, November 14, 2005

Del

Edit

Copy

Submitted by r-sowers.

Prashant Mehta (Dept. of Mechanical and Industrial Engineering, UIUC)
Dynamical Perspectives on Control of Non-Equilibrium Behavior
Abstract: Complex and chaotic non-equilibrium dynamic behavior occurs in diverse applications. Some common examples are: instabilities in aerospace applications, air-flow dynamics in buildings, non-stationary behavior in networks such as traffic networks or communication networks, dynamic biological phenomena such as replication and folding of DNA. While the field of Dynamical Systems has seen important advances in classification and analysis of such behavior, its impact on applications - particularly in nonlinear control theory - remains an open and exciting area of investigation. In this talk, I will highlight the striking interplay between Dynamics and Control. I will do so with the aid of Lyapunov functions, which are widely used for nonlinear control. I will introduce these functions, review their construction, and highlight some of their inadequacies. By combining ideas from the field of stochastic dynamics with control, I will then propose a generalization for overcoming some of these inadequacies. I will show its applicability to both stability analysis and control of non-equilibrium behavior. Results on computations and future directions for applications will also be provided.

Monday, November 28, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, November 28, 2005

Del

Edit

Copy

Submitted by r-sowers.

George Haller [email] (Dept. of Mechanical Engineering, MIT)
Nonlinear Dynamics of Aerodynamic Separation
Abstract: Flow separation (the detachment of fluid from a no-slip boundary) is a major cause of performance loss in engineering devices, including diffusers, airfoils and jet engines. In a landmark 1904 paper on boundary layers, L. Prandtl derived a criterion for flow separation in steady two-dimensional incompressible flows. Despite widespread effort, no generally applicable extension of this result has emerged for unsteady flows or even three-dimensional steady flows. In this talk, I describe an analytic criterion that predicts the location of flow separation in two-dimensional unsteady fluid flows. Based on nonlinear dynamical systems techniques, the criterion identifies separation by locating nonhyperbolic unstable manifolds that collect and eject fluid particles from the wall. I show numerical and experimental results confirming the above criterion, as well as applications of the new separation criterion to flow control. I also describe recent three-dimensional extensions of the theory.

Monday, December 5, 2005

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 2005 MEL, Monday, December 5, 2005

Del

Edit

Copy

Submitted by r-sowers.

Moshe Matalon [email] (Dept. of Mechanical Engineering, Northwestern University)
The Development of Hydrodynamically Unstable Flames
Abstract: The hydrodynamic instability, discovered independently in theoretical analyses by Darrieus and Landau over half a century ago, has many ramifications in combustion. The appearance of sharp folds and creases on the flame front of freely propagating flames, and the wrinkling observed over the surface of large spherically expanding flames are direct manifestations of this instability. The scale of the wrinkles in such circumstances is typically much larger than the characteristic cell size of the more conventional cellular flames, which result from diffusive-thermal instabilities. Furthermore, the wrinkled flame is seen to accelerate as it propagates further and may turn into a turbulent flame when reaching a sufficiently large size. The nonlinear development of hydrodynamically unstable flames has primarily relied on analytical and numerical investigation of simplified models, such as the weakly-nonlinear Michelson-Sivashinsky equation which assumes that the density change across the flame is relatively small. In this work we examine the flame evolution using a fully nonlinear model which places no restriction on the thermal expansion parameter. The computations are carried out within the context of the hydrodynamic theory, which contains fewer parameters than the full governing equations, yet permits description of multi-dimensional flames with sufficient accuracy over a wider range of conditions.

Monday, January 23, 2006

Monday, January 30, 2006

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 3405 Siebel Center, Monday, January 30, 2006

Del

Edit

Copy

Submitted by ghrist.

J. Erickson (UIUC Computer Science)
Computing Optimal Graphs on Surfaces
Abstract: The study of optimal subgraphs, such as minimum spanning trees and shortest paths, has been a staple of computer science for more than fifty years. Similarly, optimal straight-line geometric graphs, such as convex hulls and Voronoi diagrams, have been a standard object of study in computational geometry since its earliest beginnings. These optimal graph structures are critical components of countless graph and geometry algorithms. It is therefore natural to consider algorithms to compute optimal graphs in more general topological spaces. Even though embedded graphs have been a standard tool in topology for more than 100 years, relatively little is known about this class of algorithmic problem. This talk will survey algorithms for computing optimal graphs on topological surfaces, with an emphasis on open problems. For example: How quickly can we compute the shortest nontrivial cycle in a given surface? The shortest cycle in a given homotopy class? The shortest cycle that cuts the surface into two nontrivial components? The shortest graph that cuts the surface into a disk? The shortest pants decomposition? The shortest canonical homotopy basis? Neither efficient algorithms, approximations, or hardness results are known for most of these problems. For the few problems where algorithms are known, there is little reason to believe that are as fast as possible.

Monday, February 6, 2006

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 3405 Siebel Center, Monday, February 6, 2006

Del

Edit

Copy

Submitted by ghrist.

R. Ghrist [email] (UIUC Math)
How to Catch the Bad Guy
Abstract: This talk describes a new approach to pursuit-evasion games where one or more pursuers try to catch one or more evaders. Most of the known results come from differential equations or computational geometry and apply to Euclidean domains which are either planar and/or convex. This talk will introduce methods from comparison geometry which apply to non-convex domains of arbitrary dimension which satisfy a type of metric curvature constratint (cat(0) spaces). This talk will be at an elementary level and require no background in either differential games or cat(0) geometry.

Monday, February 13, 2006

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 3405 Siebel Center, Monday, February 13, 2006

Del

Edit

Copy

Submitted by ghrist.

A. Kostochka (UIUC Math)
Algorithms for equitable coloring and packing of graphs
Abstract: An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A $d$-degenerate graph is a graph $G$ in which every induced subgraph has a vertex with degree at most $d$. It is well known that trees are 1-degenerate, outerplanar graphs are 2-degenerate, and planar graphs are 5-degenerate. Our first result shows that every $d$-degenerate graph can be equitably partitioned into three $(d-1)$-degenerate graphs. Then we show that every $n$-vertex $d$-degenerate graph $G$ with $\Delta (G)\leq n/15$ can be equitably $k$-colored for any $k \ge 16d$. The proof of this bound is constructive and implies an $O(d)$-factor approximation algorithm for equitable coloring with fewest colors any $n$-vertex $d$-degenerate graph $G$ with $\Delta (G)\leq n/15$. We then extend this to an $O(d)$-factor approximation algorithm for equitable coloring of any $d$-degenerate graph. Among the implications of this result is the first $O(1)$-factor approximation algorithm for equitable coloring planar graphs with minimum number of colors. These results have applications in improved Chernoff-Hoeffding bounds for sums of random variables with limited dependence and to partitioning problems such as MAX $p$-SECTION.

Monday, February 20, 2006

Applied/Interdisciplinary Mathematics Seminar
12:00 pm in 2405 Siebel Center, Monday, February 20, 2006

Del

Edit

Copy

Submitted by ghrist.

S. MacLachlan (University of Minnesota, CS)
Coarsening in Adaptive Algebraic Multigrid
Abstract: Note: alternate time and location. This seminar is joint with the CSE Seminar.

Numerical simulation of physical processes is often constrained by our ability to solve the complex linear systems at the core of the computation. Multiscale methods, such as multigrid, provide optimal or near-optimal order solution techniques for many of these systems, relying on the use of complementary problems to reduce errors that simple iterative methods, such as Jacobi or Gauss-Seidel, are slow to resolve. Thus, classical geometric and algebraic multigrid methods rely on (implicit) assumptions about the character of these matrices in order to develop appropriately complementary coarse-grid correction processes for a given relaxation scheme. The aim of the adaptive multigrid framework is to reduce the restrictions imposed by such assumptions, thus allowing for efficient black-box multigrid solution of a wider class of problems. There are, however, many challenges in altogether removing the reliance on assumptions about the errors left after relaxation, particularly in the choice of coarse-grid points. In this talk, we introduce the adaptive AMG framework and discuss its application to problems in heterogeneous media. Recent research on purely algebraic criteria for coarse grid selection will also be discussed.

Monday, March 6, 2006

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 3405 Siebel Center, Monday, March 6, 2006

Del

Edit

Copy

Submitted by ghrist.

P. Tosic (UIUC Computer Science)
On the Computational Complexity of Counting in Certain Classes of Sparse Graph Automata
Abstract: We study computational complexity of counting the fixed point configurations (FPs), garden of Eden configurations (GEs), and predecessor configurations in certain types of graph automata. We prove that both exact and approximate counting of fixed points in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable problems. This intractability is shown to hold even when each node is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. We also show that the problems of counting exactly the garden of Eden configurations (GEs), all transient configurations, and all predecessors of an arbitrary configuration, are also computationally intractable. Moreover, the hardness of the exact enumeration of FPs and other types of configurations holds even in some severely restricted cases, i.e., when the nodes of an SDS or SyDS use at most two different Boolean functions from an appropriately restricted class of the node update rules, and, additionally, when the underlying graphs are constrained so that each node has only c = O(1) neighbors for small values of c.

Monday, March 13, 2006

Monday, March 27, 2006

Monday, April 10, 2006

Applied/Interdisciplinary Mathematics Seminar
3:00 pm in 3405 Siebel Center, Monday, April 10, 2006

Del

Edit

Copy

Submitted by hirani.

Pavel Bochev (Sandia National Lab, Computational Mathematics and Algorithms)
Mimetic Discrete Models with Weak Material Laws, or Least Squares Principles Revisited
Abstract: To a casual observer, compatible (or mimetic) methods and least squares principles for PDEs are polar opposites. Mimetic methods inherit key conservation properties of the PDE, can be related to a naturally occurring optimization problem, and require specially selected, dispersed degrees of freedom. The conventional wisdom about least squares is that they rely on artificial energy principles, are only approximately conservative, but can work with standard C0 nodal (or collocated) degrees of freedom. The latter is considered to be among the chief reasons to use least squares methods. In this talk we demonstrate that exactly the opposite is true about least-squares methods. First, we will argue that nodal elements, while admissible in least squares, do not allow them to realize their full potential, should be avoided and are, perhaps, the least important reason to use least squares! Second, we will show that for an important class of problems least squares and compatible methods are close relatives that share a common ancestor. In fact, we will prove that in some circumstances, least squares and compatible methods compute identical answers. The price paid for gaining favorable conservation properties is that one has to give up what is arguably the least important advantage attributed to least squares methods: one can no longer use C0 nodal elements for all variables. To carry out this agenda we use algebraic topology to guide our analysis and develop a common framework for compatible discretizations. Using a reduction and a reconstruction maps between differential forms and cochains we define mutually consistent sets of natural and derived discrete operations that preserve the invariants of the DeRham homology groups and obey a discrete Stokes theorem. By choosing a specific reconstruction operator we obtain well-known mixed FE, mimetic FD and covolume methods and explain when they are equivalent. The key concept in our approach is the natural inner product on cochains. This inner product is sufficient to generate a combinatorial Hodge theory on cochains but avoids complications attendant in the construction of robust discrete Hodge-star operators. For problems that require approximations of material laws we employ equivalent constrained optimization problems that enforce the laws weakly, instead of using their explicit discretization. We then consider three possible mimetic discretizations of the optimization problem. Two of them give familiar Galerkin and/or mixed type methods. The third one reduces the optimization problem to a mimetic least squares principle whose minimizers are, under certain conditions, identical with the solutions of the other two mimetic discretizations. We conclude by a series of numerical examples that assert our findings. This talk is based on joint work with M. Gunzburger (CSIT, Florida State University) and M. Hyman (Theoretical Division, Los Alamos National Laboratory). Host : Anil Hirani (UIUC Computer Science)