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).
Cancelled.
Speaker: Kevin Lin, University of Arizona, Mathematics Dept.
Title: Reliability of coupled oscillators
Abstract: This talk concerns the reliability of coupled oscillator networks in response to complex, fluctuating stimuli. Reliability means that repeated presentations of a stimulus elicit essentially identical responses regardless of the system's state at the onset of the input. This work is motivated by basic questions from neuroscience, where the reliability of a network is relevant to how information may be encoded and transmitted. I will show how the question of reliability can be precisely formulated in the framework of random dynamical systems theory, and review the well-known fact that single phase oscillators are reliable. I will then show that unreliability can occur even in a 2-oscillator system, and propose a geometric mechanism for the observed phenomena. The talk will conclude with some observations concerning larger networks, including a natural condition which precludes unreliability. No prior knowledge of random dynamical systems theory is assumed. This is joint work with Eric Shea-Brown and Lai-Sang Young.