The superlinear O(N log N) time requirement is the bottleneck for the Fast Fourier Transform (FFT) to process huge amount of data. We analyze a sublinear RAlSFA (Randomized Algorithm for Sparse Fourier Analysis) that finds a near-optimal B-term Sparse Representation R for a given discrete signal S of length N, in time and space poly(B,log(N)) (instead of O(N logN)). A straightforward implementation of the RAlSFA, as presented in the theoretical paper by Gilbert, Guha, Indyk, Muthukrishnan and Strauss, turns out to be very slow in practice. Our main result is a greatly improved and practical RAlSFA (more than a factor of 4000 times faster than original algorithm!). It beats the FFTW for reasonably large N. We also extend the algorithm to higher dimensional cases. The crossover point lies at N~70000 in one dimension, and at N~ 900 for data on a N*N grid in two dimensions for small B signals. We also find this algorithm is very robust to the noise.

Shear flow in fluids and plasmas brings about non-Hermiticity in the linear dynamics of fluctuations. As a consequence, a degeneracy of continuous spectra may lead to the algebraic growth of perturbation (secularity) even if all eigenvalues of generator are real. We will show that Rayleigh equation (governing equation for Kelvin-Helmholtz instability) with piecewise linear shear-flow profile contains a ``resonance' (frequency overlapping or degenerate frequency) between surface wave and ballistic response when the system is stable for Kelvin-Helmholtz mode. Normally, perturbed field may be stable in spite of the resonance, while it must be retained in the rigorous expression of the generator. When plasma oscillation (or internal gravity wave) is coupled with Rayleigh equation, another ballistic mode couples with the resonance and the perturbed density (or vorticity) asymptotically shows locally secular behavior. The secularity is decelerated to linear growth in time while the degeneracy of the spectra looks third order between single point and two continua. It is also shown by renormalization technique that the deceleration is attributed to the continuum damping of the point spectra.

In this talk, we will describe some key problems in medical imaging especially registration and surface warping. This will be based on the Monge-Kantorovich theory of optimal mass transport. Further, many of the algorithms in medical imaging are based on curvature driven flows implemented via level set methods. We will describe a new stochastic interpretation of such flows based on the theory of hydrodynamic limits. We will try to make the talk accessible to a broad audience with an interest in mathematical medical imaging. All of the methods will be illustrated with real image data.

Joint CSCAMM/Mathematics Seminar

In this talk we will first describe the general framework of high order weighted essentially non-oscillatory (WENO) finite difference schemes for solving hyperbolic conservation laws and in general convection dominated partial differential equations. We will then discuss our recent effort in designing anti-diffusive flux corrections for these high order WENO schemes. The objective is to obtain sharp resolution for contact discontinuities, close to the quality of discrete traveling waves which do not smear progressively for longer time, while maintaining high order accuracy in smooth regions and non-oscillatory property for discontinuities. Numerical examples for one and two space dimensional scalar problems and systems demonstrate the good quality of this flux correction. High order accuracy is maintained and contact discontinuities are sharpened significantly compared with the original WENO schemes on the same meshes. We will also report the extension of this technique to solve Hamilton-Jacobi equations to obtain sharp resolution for kinks, which are derivative discontinuities in the viscosity solutions of Hamilton-Jacobi equations. This is joint work with Zhengfu Xu.

Beginning from a kinetic description for a fully ionized Hydrogen plasma with a simple collisional model, fluid approximations are derived in a scaling where the gyrofrequency are comparable to the collision frequency. One obtains strongly anisotropic viscous and thermal transport, and anisotropic dispersive corrections to classical MFD models. Moreover, these approximations respect entropy relations.

Developing reliable strategies for controlling the assembly of small objects into functional structures is of great interest. We will focus on our recent efforts in this area and focus on a particularly beautiful example of V. Manahoran and D. pine in which small spheres are assembled into precise configurations through drying of interstital fluid. For a given number of spheres the structures that formed form uniquely corresponded to the sphere packing that minimized the second moment of the particle distribution. I will focus on our efforts to understand these results, focusing on the important role of geometrical constraints.

The theory of fracture usually referred to as that of Griffith shows many drawbacks: it does not initiate cracks; it is powerless when trying to predict the crack path; it does not know how to handle sudden crack jumps, ..... Jean-Jacques Marigo and I have proposed a model based on energy minimization which does away with many of those obstacles, while departing as little as feasible from Grifffith's theory.

I will first describe the proposed model, show how it does away with the above mentioned drawbacks and evoke its specific shortcomings.

From a mathematical stanpoint, the model resembles a kind of evolutionary image segmentation problem in the sense of Mumford & Shah. Chris Larsen and I have shown the existence of a solution to the evolution for the weak -à la De Giorgi - formulation of the problem. I will briefly describe the result, the method that was used in the proof and also mention the non-trivial extensions to the case of a non-convex bulk energy, obtained in collaboration with Gianni Dal Maso and Rodica Toader.

The model is readily amenable to numerics through various regularization of the energy which Gamma-converge to the original energy. This is the work of Blaise Bourdin ( partly in collaboration with Antonin Chambolle). For lack of time, I will not discuss numerical issues, which are fascinating, but merely illustrate the talk with Bourdin's latest 2 and 3-d. computations.

If time permits, I will show how the adoption of a cohesive surface energy and of a more lenient minimization criterion cures the shortcomings of the variational Griffith model and even bridges the mysterious gap between fracture and fatigue. This is the path actively pursued by Jean-Jacques Marigo at the present time. The numerics and 1d-results are very promising but the mathematical results are yet very primitive.

Thierry Goudon, CNRS-Université des Sciences et Technologies de Lille

Modeling of fluid/particles interactions

We consider a cloud of particles, subject to a friction force exerted by a surrounding fluid. The evolution of the particles is described by a distribution function in phase space f(t, x, v) 0; the evolution of which is governed by

δ_tf + ∇_x(vf) + δ_v(Ff) = Q(f)

F(t, x, v) = ((6πμa)/M) / (v − u(t, x))

where u(t, x) stands for the velocity field of the fluid. This is the referred to as the Stokes force. It is proportional to the relative velocity (v − u), the proportionality coefficient involving the viscosity μ > 0 of the fluid, the radius a > 0 and the mass M of a particle: M = 4/3πa³ ρ_P, ρ_P being the mass density of the particles.

We are concerned with two differents questions. The former is concerned with the effect of high variations of the (given) fluid velocity, intended to mimic turbulence effects. The latter is concerned with coupled models involving evolution equations for the fluid velocity; then, we investigate various asymptotic regimes, depending on the value of physical constants.

This is a survey of joint works with Frédéric Poupaud, Alexis Vasseur, Pierre-Emmanuel Jabin, José-Antonio Carrillo (ICREA-UAB, Barcelona).

We introduce a new preconditioning technique for iteratively solving linear systems arising from finite element discretizations of the mixed formulation of the time-harmonic Maxwell equations, with small wave numbers. The preconditioners are based on discrete regularization, and are motivated by spectral equivalence properties of the discrete operators. We show that using the scalar Laplacian as a weight matrix for regularization leads to an effective block diagonal preconditioner, for which fast iterative solution methods can be applied. The main computational cost is related to solving a linear system whose associated matrix is the discrete curl-curl operator, shifted (approximately) by the vector mass matrix. The analytical observations are accompanied by numerical results that demonstrate the scalability of the technique.

The refinement of quantities of interest (goal or cost functionals) using adjoint (dual) parameters and a residual is at present a well established technology. The truncation error may be estimated via the value of residual engendered by the action of a differential operator on some extrapolation of the numerical solution. The adjoint approach allows accounting for the impact of truncation error on a target functional by summation over the entire calculation domain.

Numerical tests demonstrate the efficiency of this approach for smooth enough physical fields (heat conduction equation and Parabolized Navier-Stokes (PNS)). The impact of solution smoothness on the error estimation is found to be significant. However, the extension of this approach to discontinuous field is also feasible. We can handle the error of discontinuous solution (Euler equations) using the solution for viscous flow (PNS) as a reference. The influence of viscous terms may be accounted for using adjoint parameters. Results of numerical tests demonstrate applicability of this approach.

Thanksgiving
 

We address the problem of representing and manipulating non-manifold multi-dimensional shapes described by simplicial complexes. Simplicial complexes are widely-used shape representations in a variety of applications, including computer graphics, solid modeling, terrain modeling, visualization of scalar and vector fields, finite element analysis. The major driving application for our work has been modeling finite element meshes generated from CAD models through an idealization process. In this talk, we present different representations for non-manifold shapes, described by simplicial complexes, that we have developed in our work. We analyze and compare such representations, based on their expressive power, on their storage requirements, and on their effectiveness in supporting navigation and update operations. We first discuss two compact and scalable representations specific for two- and three-dimensional simplicial complexes embedded in the 3D Euclidean space, and a dimension-independent representation for simplicial complexes in arbitrary dimensions. We then present an approach to modeling non-manifold multi-dimensional shapes based on a unique decomposition of a shape into nearly manifold components. This decomposition is not only an effective model for developing compact and dimension-independent data structures for non-manifold multi-dimensional shapes, but it also provides a suitable tool for performing geometric reasoning on such shapes.

We model the immune dynamics between T cells and cancer cells in leukemia patients after bone marrow transplants. Our approach incorporates time delays and accounts for the progression of cells through different modes of behavior. We explore possible mechanisms behind a successful cure, whether mediated by a blood-restricted immune response or a cancer-specific graft-versus-leukemia effect. Characteristic features of this model include sustained proliferation of T cells after initial stimulation, saturated T cell proliferation rate, and the possible elimination of cancer cells, independent of fixed-point stability. In addition, we use numerical simulations to examine the effects of varying initial cell concentrations on the likelihood of a successful transplant. Among the observed trends, we note that higher initial concentrations of donor-derived, anti-host T cells slightly favor the chance of success, while higher initial concentrations of general host blood cells more significantly favor the chance of success. These observations lead to the hypothesis that anti-host T cells benefit from stimulation by general host blood cells, which induce them to proliferate to sufficient levels to eliminate cancer. This is a joint work with R. DeConde, P. Kim, and P. Lee.

*NOTE SPECIAL DAY AND TIME*

MONDAY 12th Dec at 3:00PM

I will present some recent work in collaboration with Igor Rodnianski concerning a breakdown criterion in General Relativity. An essential ingredient of the work is to get a lower bound on the radius of injectivity of null hypersurfaces which are boundaries of future or past sets of points in Ricci flat Lorentzian metrics, This is used in conjunction with a Kirchoff-Sobolev type formula in Lorentzian geometry.