Applied Math. Seminar, Fall 2007

Back to Applied Math seminar webpage

**September 6: SPECIAL DATE and TIME, 4:15pm-5:20pm**

Speaker: Gregory Gutin,
Royal Holloway, University of London - Department of Computer Science

**Title: **Worst Case Analysis of Greedy, Max-Regret and Other Heuristics
for Multidimensional Assignment and Traveling Salesman Problems

**Abstract: ** Combinatorial optimization heuristics are often compared with
each other to determine which one performs best by means of worst-case
performance ratio which reflects the quality of returned solution in the worst
case. The domination number is a complement parameter indicating the quality of
the heuristic in hand by determining how many feasible solutions are dominated
by the heuristic solution.

We prove that the Max-Regret heuristic introduced by Balas and Saltzman finds
the unique worst possible solution for some instances of the
*s*-dimensional (*s*≥3) assignment problem (*s*-AP) and the
asymmetric traveling salesman problems (ATSP) of each possible size. It was
proved earlier that Greedy has the same property for ATSP and it's not
difficult to show that Greedy has the same property for *s*-AP
(*s*≥2). This means that the domination number of all above mentioned
heuristics (for ATSP and *s*-AP) is 1.

We show that the Triple Interchange heuristic (for *s*=3) also introduced
by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching)
have factorial domination numbers for *s*-AP (*s*≥3). ATSP
heuristics of factorial domination number will also be discussed.

The results of preliminary computational experiments with our heuristics will
be shown.

(joint work with B. Goldengorin and J. Huang)

**September 10:**

Speaker: François Willot, Mechanical Engineering and Applied Mechanics, University of Pennsylvania

**Title: ** Strain localization and effective medium properties
in 2D perfectly-plastic porous materials: the "dilute" limit

**Abstract: **This work addresses a notoriously difficult problem of nonlinear behavior and infinite contrast between two phases, one of which is a plastic solid phase, and the other one the porosity of the medium. Such problem is of special interest to effective-medium approximations, which typically reach their limits in situations of strong nonlinearity and high contrast between the phases. The aim of this study is to investigate how plastic strain localization manifests itself at the level of the overall effective behavior of the medium in presence of pores, and in particular in the non-trivial limit of small porosity. This question, important to the understanding of ductile damage, is examined both numerically and theoretically, in the special case of two dimensional systems, and with a deformation-theory approach of plasticity. The numerical investigations consist of quasi-exact computations of the stress and strain fields in the voided medium, by means of the Fast Fourier Transform method making use of a particular choice for Green's function. The theoretical approach makes use of exact solutions, which can be obtained in particular cases of a periodic void lattice, as well as of a recent "second-order" nonlinear homogenization approach. The virtues of the latter are evaluated in two steps, first by studying the underlying linear anisotropic homogenization step (an essential ingredient), then by studying the nonlinear step itself. A connection between the strain/stress localization patterns and the macroscopic behavior is shown in the case of a strongly anisotropic linear material. In the nonlinear case, the nature and significance of the singularities, confirmed by FFT computations, are partly elucidated.

**September 24:**

Speaker: Fernando Guevara Vasquez, University of Utah - Dept. of Mathematics

**Title: ** Electric impedance tomography with resistor networks

**Abstract: **
Electric impedance tomography consists in finding the conductivity inside a
body from electrical measurements taken at its surface. This is a severely
ill-posed problem: any numerical inversion scheme requires some form of
regularization. We present inversion schemes that address the instability of
the problem by seeking a sparse parametrization of the unknown conductivity.
Specifically, we consider finite volume grids of size determined by the
measurement precision, but where the node locations are to be determined
adaptively. A finite volume discretization can be thought of as a resistor
network, where the resistors are essentially averages of the conductivity over
grid cells. We show that the model reduction problem of finding the smallest
resistor network (of fixed topology) that can predict meaningful measurements
of the Dirichlet-to-Neumann map is uniquely solvable for a broad class of
measurements. We propose a simple inversion method that is based on an
interpretation of the resistors as conductivity averages over grid cells, and
an iterative method that improves such reconstructions by using sensitivity
information on the changes in the resistors due to small changes in the
conductivity. A priori information can also be incorporated to the latter
method.

**October 22: CES-CSAFE Seminar (SPECIAL TIME AND LOCATION: 3PM in Warnock Engineering Building 2230)**

Speaker: Marsha Berger, New York University, Computer Science Department

**Title:** Cartesian Cut Cell Methods: Where Do Things Stand?

**Abstract: ** (From the SCI Seminar series)

We discuss some of the steps involved in preparing for and
carrying out a fluid flow simulation in complicated geometry.
Our goal is to automate this process as much as possible to enable
high quality inviscid flow calculations. We use multilevel Cartesian
meshes with irregular cells only in the region intersecting a solid
object. We present some of the technical issues involved in this
approach, including the special discretizations needed to avoid loss of
accuracy and stability at irregular boundary cells, as well as how we
obtain highly scalable parallel performance. This method is in routine
use for aerodynamic calculations in several organizations, including the
NASA Ames Research Center. Many open problems are discussed.

**October 29:**

Speaker: Jeff Blanchard, University of Utah,
Mathematics Dept.

**Title: ** Composite Dilation Wavelets

**Abstract: ** We will begin by recalling the basic properties of wavelets
including the structure of a multiresolution analysis (MRA). Wavelets are
limited in certain applications due to the rigid geometry of their support
sets. A recent answer to this rigidity introduced by Guo, Labate, Lim, Weiss,
and Wilson is a true generalization of wavelets, Composite Dilation Wavelets.
These affine systems use two sets of dilations, one expanding and one a group
action on R^n. We will discuss how the basic properties of wavelets including
the MRA extend to the composite dilation setting. Via examples, we will discuss
some significant advantages to the composite dilation systems including
non-separable, singly generated, Haar-type wavelets. Time permitting we will
discuss the existence of a very large family of minimally supported frequency
composite dilation wavelets in every dimension.

**November 5:**

Speaker: Valy Vardeny^{*}, University of Utah - Physics Department

**Title: ** Experimental Studies of Plasmonic Metamaterials

**Abstract: **
Artificially structured materials, or “metamaterials”, with
properties not present in naturally occurring materials have attracted
significant interest in recent years because their potential to revolutionalize
our understanding of the dielectric function and consequent optical response of
these structures. Three dimensional (3D) metallic photonic crystals, and 2D
periodic and aperiodic arrays of subwavelength apertures on metal films are two
specific examples of such media. The subwavelength nature of the active surface
plasmon polariton (SPP) excitations in such metamaterials, along with strong
field localization open up novel applications in bio-sensing, guided-wave
devices and quantum optics.

Our work has been primarily focused on the fundamental investigation and
development of 2D and 3D plasmonic metamaterials that are active in the
visible, near infrared and terahertz (THz) frequencies. We fabricate 3D
metallo-dielectric photonic crystals based on metal infiltrated opal photonic
crystals, and measure their optical and thermal emission properties. We also
fabricate 2D subwavelength aperture arrays (plasmonic lattices) and use THz
time-domain spectroscopy (THz-TDS) to measure their extraordinary transmission
properties. We demonstrate that aperture *periodicity* is not crucial for
obtaining strong transmission resonances through these 2D structures, by
measuring the transmission properties of various “*designed*”
aperture arrays that include quasicrystals and quasicrystal approximates. We
found, however that the thermal emission properties of plasmonic lattices are
not fundamentally different than that of non-perforated metal films, except for
an ‘optical filtering’ effect.

Furthermore, the THz-TDS method that we use allows for a direct measurement of
the THz electric field transmitted through the plasmonic lattices, yielding
both amplitude and phase information. Hence the complete complex dielectric
response of these complex media can be directly measured without resorting to
Kramers-Kronig relation. By treating periodic and aperiodic aperture arrays as
“effective” plasmonic media in the THz beam path, we demonstrate the
ability to engineer the dielectric function of such structures. This may prove
important in understanding the dielectric properties of a broader range of
metamaterials.

* In collaboration with Profs. Efros and Nahata; Drs. Dewkar, Matsui, Pokrovsky
and Kamaev; and Mr. Agrawal.

**November 19:**

Speaker: Frederic Noo, University of Utah - Utah Center for
Advanced Imaging Research

**Title: ** An excursion into the mathematics of image reconstruction in
single photon emission computed tomography

**Abstract: **
Single photon emission computed tomography (SPECT) is a particular imaging technique that allows visualization of the distribution of a radio-active tracer in a body in a non-invasive way. In this talk, will review the fundamental equations that relate measurements that can be taken to this distribution, and discuss various ways to recover the distribution from the measurements.

__ November 28: Joint with the Bio-math seminar, SPECIAL DATE AND TIME (Wednesday at 3:05pm in LCB 215)__.

Speaker: Kevin Lin, University of Arizona, Mathematics Dept.

155 South 1400 East, Room 233, Salt Lake City, UT
84112-0090, T:+1 801 581 6851, F:+1 801 581 4148