Applied and Computational Mathematics Seminar, Spring 2003

Scope

Mission

Schedule

Tuesday 3 June, 3:10-4pm in 320 Morton Hall:
Introducing MOMRA - a multi-resolution analysis that leads to a shift-invariant discrete wavelet transform, Xunming Du (Mathematics)

The classical Discrete Wavelet Transform (DWT) can be used to decompose a sequence representing a signal into multiple components. However, this decomposition is not shift invariant in that, even for periodic signals, the decomposition strongly depends upon which value is considered to be the first value of the sequence. This creates a problem in using the DWT to analyze a stationary time series, where one would want the decomposition to be independent of the starting point. In this talk, we will describe the Maximal Overlap DWT (MODWT), a variation of the DWT that is shift invariant. We discuss some of the differences between the MODWT and DWT. We will also introduce a variation of (and give partial results on) a multi-resolution analysis of L2(R), the `MOMRA', that leads to the MODWT in the same fashion that the classical multi-resolution analysis leads to the DWT.

Tuesday 27 May, 3:10-4pm in 320 Morton Hall:
Hierarchical Clustering via Joint Between-Within Distances, Maria Rizzo (Mathematics)

We present a new algorithm for hierarchical clustering based on a joint between-within measure of distance between clusters. In contrast to some standard clustering methods, which minimize within cluster distance, or maximize between cluster distance, the between-within distance jointly measures both the between and within distances. Application of the clustering procedure is demonstrated with examples, and solutions are compared with the average linkage method and Ward's method. Empirically, the proposed method compares very favorably with the standard methods. The method based on between-within distance has the following advantages: consistency, ultrametricity, space-dilating property, and computational simplicity.

Tuesday 20 May, 3:10-4pm in 320 Morton Hall:
Testing the War of Attrition model with computer simulations, Fang Zhu (Mathematics)

The War of Attrition model of John Maynard Smith predicts a single, mixed evolutionarily stable strategy (ESS) for animal contests which are settled by conventional displays with no assessment of the opponent's fighting ability. We test the predictions of the model by simulating the evolution of strategies in a finite population of animals under various assumptions on how possible strategies are coded and mutated. While our simulations for the most part confirm the predictions of the model, we also discovered some significant deviations from the theoretically predicted ESS. Specifically, we found that if inheritance of strategies is somewhat imprecise, then a population can evolve that achieves on average a higher payoff than a population at the theoretically predicted ESS. Moreover, if the ESS is realized as a polymorphism of fixed displaying times, then for small populations, sufficiently stringent statistical tests will reject the hypothesis that these times are distributed as theoretically predicted.

Tuesday 13 May, 3:10-4pm in 320 Morton Hall:
Slow Passage Through Bifurcation in Hamiltonian Systems (part 2), Todd Young (Mathematics)

Consider a system with Hamiltonian H(q,p,lambda), where lambda is a slowly varying parameter, i.e. (d/dt)lambda = O(epsilon). If the system has one degree of freedom then a classical result says that the action, I, is an adiabatic invariant. That is |I(t) - I(0)| = O(epsilon) for t in [0,1/epsilon]. This result requires the assumption that trajectories are oscillatory and the ``frequency" stays bounded away from 0. In the seventies, Neistadt and others showed that part of this result can be retained if the frequency passes through 0 by way of crossing a seperatrix of a saddle fixed point. In particular, suppose that H(q,p,lambda) = H(-q,p,lambda), then the region of interest in phase space, U can be decomposed into two regions, V and W with the following properties: 1. The measure of W is small to all orders in epsilon, and 2. For all initial conditions in V, we have |2I(T) - I(0)| = O(sqrt(epsilon) log(epsilon)), where T = 1/epsilon. Neistadt's proof uses the averaging method and is very difficult. The averaging method cannot be generalized to higher degree of freedom problems. Further, Neistadt made non-generic assumptions about the local form of the equations near the saddle point.
  In this second talk I will emphasize some details of the numerical studies on the separatrix crossing. The numerical methods used will be familiar to most students, but the way they are applied is non-trivial.

Tuesday 6 May, 3:10-4pm in 320 Morton Hall:
Wavelet Analysis of Time Series, Jeffery Connor (Mathematics)

This talk is an introduction into wavelet-based techniques in the analysis of time series. There will be a review of multi-resolution analysis and wavelets with an eye towards extracting information from time series of economic data. As time permits, the maximal overlap discrete wavelet transform will be introduced as a tool to analyze the variance of a time series.

Wednesday 30 April, 3:10-4pm in 320 Morton Hall:
Saving k colors in polynomial-time, David Juedes (Electrical Engineering and Computer Science)

This talk examines general techniques for kernelization by exploring combinatorial properties of maximum matchings. Briefly, kernelization is the technique of parameterized data reduction where a problem instance <I,k> is reduced to an equivalent problem instance <I',k'> with |I'| ≤ f(k) and k' ≤ k. These techniques are employed to show that the Dual of Graph Coloring admits a 3k-3 kernel, i.e., that the problem of determining whether a graph G can be colored using |V| - k colors can be reduced to the problem of determining whether a graph G'=(V',E') of size ≤ 3k-3 can be colored using |V'| - k' colors. The same approach is used to give a 3k kernel for Vertex Cover.

Tuesday 22 April, 3:10-4pm in 320 Morton Hall:
Approximation algorithms for network design problems (part 2), Vardges Melkonian (Mathematics)

Survivable network design problems concern the design of those kind of networks that remain functional even if some of their elements (edges, nodes) are broken. Network design problems arise from many sources, including the design of various transportation systems (such as highways and mass-transit systems) as well as telephone and computer networks. The network design problems that we consider are NP-hard; so our goal is to find efficient approximation algorithms for them. While in the last 10 years there has been significant progress in designing approximation algorithms for undirected network design problems little progress has been made on their directed counterparts. The main goal of our work is to explain the difficulties intrinsic to directed networks and to give new algorithms for them. The specific network design problem we consider here is the following: find a minimum cost subgraph such that for each vertex set S there are at least f(S) arcs leaving S. The algorithms we design for these problems are the the primal-dual method and its variations. We give theoretical guarantees for the performance of our algorithms and also present computational results which support their good performance in practice. (This is joint work with Eva Tardos.)

Tuesday 15 April, 3:10-4pm in 320 Morton Hall:
Sampling theory for Wavelets (part 2), Annie Shen (Mathematics)

Beginning with a brief review of some properties for wavelets, this talk focuses on the discussion of two groups of sampling theory: Shannon-like sampling theory in wavelet subspaces for band-limited wavelets; The positive sampling using a hybrid sampling sequence.
 This talk is partly based on a joint article with Gilbert G. Walter, Positive Sampling in Wavelet Subspaces, Journal of Applied Computational Harmonic Analysis, Vol. 12, No. 1, January 2002, pp. 150-165 (available at http://www.math.ohiou.edu/~shen/articles.html)

Tuesday 8 April, 3:10-4pm in 320 Morton Hall: Organizational Meeting

Winter 2003 schedule.