[+] Team 1: Steady-state Simulation of Large Nonlinear Systems

**Mentor** Robert Melville, Alcatel-Lucent Technologies Bell Laboratories- Danny Dunlavy, Western Michigan University
- Sookyung Joo, Purdue University
- Runchang Lin, Wayne State University
- Roummel Marcia, University of California, San Diego
- Aurelia Minut, Michigan State University
- Jianzhong Sun, Purdue University

Large systems of coupled non-linear ordinary differential equations arise naturally in applications areas like design of radio-frequency integrated circuits and vibration analysis of mechanical structures. Of particular interest is the steady-state response of a non-linear system to periodic stimulus -- i.e., the response after any start-up transient has died down. Various classic RF (radio-frequency) measurements -- such as compression point or intermodulation -- only make sense in steady state. The response to quasi-periodic stimulus (two frequencies which are not rationally related) is of special interest in radio work. Exact or even approximate "closed form" solutions of such systems is impossible for realistic examples, due to the size of the problem and the complexity of non-linear models. However, numerical solutions can be highly effective.

The methods of Harmonic Balance or Finite Differencing replace the system of ODEs with a system of non-linear equations using discretization and a suitable numerical approximation to the time derivative. However, the system of equations becomes much larger. If the original system of ODEs had m waveforms (typical m: 100 to 1000) and n discretization points are used (typical n: 32 to 1024) then a solve of m*n non-linear equations in m*n unknowns is required. The dimension of this system can exceed 100,000(!). A numerical method, such as Newton's method, is used to solve the system. Each step of Newton's method (the so-called "outer" iteration) requires the solution to a system of linear equations of the same size as the non-linear system. Conventional Gaussian elimination would flounder on a system of such size. However, the special structure of the linear system allows a very fast matrix-vector product. Therefore, iterative linear solves can be used (the so-called "inner" iteration) to compute the solution to the linear problem needed for each step of Newton's method. The memory and time savings possible with such iterative linear solves is enormous and enables solution of practical problems of a size which was considered unapproachable a few years ago.

I plan to have participants implement a complete steady-state simulation code using iterative linear solves for the inner iteration. I will provide some of the supporting environment for this project and will supply several realistic example problems. Then, various ideas from the theory of structured matrices will be introduced including Toeplitz and circulant matrices, Tensor products, multi-dimensional Fourier transforms and matrices of low displacement rank. Using these concepts, participants will be asked to develop new ideas for improving the performance of the implementation, and try out their ideas on the suite of test problems. No particular knowledge of electrical engineering will be assumed, but participants should be strong programmers comfortable with numerical methods in either C or Fortran. We will begin immediately to look at "industrial strength" examples, large enough so that both asymptotic performance and constant speed improvements are important.

**Selected references:**

Steady-state Methods for Simulation Analog and Microwave Circuits, K. Kundert, J. White, A. Sangiovanni-Vincentelli, Kluwer Academic Publishers, 1990.

Mathematics of Multi-dimensional Fourier Transforms, R. Tolimieri, M. An, C. Lu, Springer-Verlag, 1993.

IEEE Custom Integrated Circuits Conference (CICC); years 95,96,97; Long,Feldmann,Roychowdhury,Horton,Ashby,Melville.

Iterative Methods for Sparse Linear Systems, Y. Saad, PWS Publishing, 1996.

[+] Team 2: Optimizing Language Models and Texts for Automatic Speech Recognition

**Mentor** Joan Bachenko, Linguistic Technologies, Inc.- Suzanne (Hruska) Boyd, Indiana University
- Maria Kiskowski, University of Notre Dame
- Jennifer Lefeaux, North Carolina State University
- Kevin McCleary, Kent State University
- Dany Ngouyassa, Indiana University
- Bryan Smith, Tufts University

Speech recognizers incorporate three core modules: the decoder, which performs pattern matching; the language model, which defines the vocabulary and word patterns; and the acoustic model, which defines the phone set and phone patterns. The process of recognition is essentially a series of guesses among thousands of hypotheses. The job of language and acoustic models is to represent the hypotheses and their likelihood in order to maximize the recognizer's chances of getting the right output for speech input. This workshop will focus on language modeling and on experiments in language model optimization. Training data, language model software and access to a high quality speech recognizer will be made available to participating students.

A language model (LM) is a probabilistic model trained on text data. Most LMs today are trigram models (where "gram" is a word) that back off to bigrams and unigrams and use a smoothing technique to handle sparse data. For working speech recognition systems, the LM is only as good as the text that it trains on. Hence texts are usually taken from some limited domain, e.g. airline reservations or radiology, in order to constrain the set of hypotheses that the LM makes available. If the training text is too limited, however, the LM will fail to represent ngrams that are likely to be spoken.

One question we will be addressing in the workshop is how to determine when a training text is sufficiently good for producing a good LM. Another question we will address is how to partition a training text into minimally overlapping sublanguage texts in order to build good sublanguage models. For example, is it possible to predict whether the best LM includes both pediatrics and general medicine or whether the recognizer will perform better with two distinct LMs; if the best approach is two LMs, then how should the distance between them be measured and optimized? The workshop will focus on lexical growth and LM interpolation in an attempt to provide some answers to these questions. Lexical growth is a measure of the rate at which new words are observed in a text as the text grows in size. Predictive models of lexical growth exist and will be discussed. LM interpolation is a statistical method of weighting texts in LM construction. Although interpolation is commonly used in adapting LMs to new domains, little is known about how interpolation can be used to predict LM performance.

**References**:

Internet:

Speech at Carnegie-Mellon University: http://www.speech.cs.cmu.edu/index.html This is one of the best toolkits for building LMs for research. You can download the CMU Statistical Language Modeling Toolkit and read the documentation.

Speech at Cambridge University: http://svr-www.eng.cam.ac.uk/research/speech Click on Links to Related Sites to visit other speech recognition laboratories. Cambridge is closely connected to Entropic Cambridge Research Laboratory, which produces a highly regarded speech recognizer called HTK (Hidden Markov Model Toolkit).

Center for Language and Speech Processing at Johns Hopkins University: http://www.clsp.jhu.edu Follow the links to workshops.

Reading:

Allen, James. 1995. Natural Language Understanding. Redwook City, CA: Benjamin/Cummings Publishing. Chapter 7 and Appendix C.

Jurafsky, Dan and James H. Martin. 2000. Speech and Language Processing. Englewood Cliffs, NJ: Prentice-Hall. Chapters 5, 6, 7.

[+] Team 3: Computer Aided Design: The Surface Intersection Problem

**Mentor** Thomas Grandine, The Boeing Company- Bogdan Craciun, California Institute of Technology
- Noel Heitmann, University of Pittsburgh
- Brian Ingalls, Rutgers, The State University of New Jersey
- Quoc Legia, Texas A & M University
- Miao-Jung Ou, University of Delaware
- Richard Tsai, University of California, Los Angeles

The surface intersection problem is one of the fundamental algorithms in Computer-Aided Design and Solid Modeling. The main computational difficulties arise because the solution may have multiple components, and it's not always clear when all components have been found. In the workshop, we'll focus on solving the surface intersection problem by treating it as a contouring problem which can in turn be solved numerically via a differential-algebraic equation formulation.

If time permits, we can turn our attention to some more open-ended issues regarding contouring, in particular the idea of generating contour surfaces by solving more general partial differential algebraic equations in higher dimension than was done for the surface intersection problem. Such an ability would be very useful in terms of performing swept volume and swept surface computations.

**References:**

The two main references for this are:

"A New Approach to the Surface Intersection Problem," (with F. W. Klein IV) Computer Aided Geometric Design 14, pp. 111-134 (1997)

"Applications of Contouring," SIAM Review 42, to appear in Spring, 2000.

[+] Team 4: Computed Tomography

**Mentor** Sarah Patch, General Electric- Jicun Hu, Marquette University
- Chris Ingrassia, New York University
- Svenja Lowitzsch, Texas A & M University
- Jang Park, Northwestern University
- Angel Pineda, University of Arizona
- Daniel Reynolds, Rice University
- Nicolas Valdivia, Wichita State University

Computed tomography (CT) generates images of a patient's density. Data is collected by sending x-ray radiation through the patient. The ratio of transmitted to incident radiation represents the line integral of the patient's density, (since radiation travels in straight lines through the patient. CT data is subject to consistency conditions, both integral (Helgason-Ludwig) and differential (Fritz John). CT systems measure characteristic data for John's ultrahyperbolic equation

u_{x1,x1} + u_{x2,x2} = u_{y1,y1} + u_{y2,y2}

By solving the characteristic boundary value problem for John's equation we can compute unmeasured CT data within the characteristic cone from measured data on the boundary. Computing additional data give us tremendous flexibility in choice of reconstruction algorithm, (but cannot provide additional information about the imaging object). We will discuss - and hopefully improve - numerical methods for solving John's equation for third-generation and open-gantry systems. Practically, total flop count is not as important as run-time (data flow is very important!) Also, reconstruction algorithms do not require measuring all lines through the object for a mathematically exact reconstruction. Therefore, we need only compute some of the missing views accurately. Optimizing image quality and total reconstruction time is an open problem.

**References:**

Dym & McKean, "Fourier Series and Integrals", especially the section on the Radon transform.

"Practical Cone Beam Algorithm," by Feldkamp, Davis and Kress, JOSA vol 1, no 6 gives the nuts and bolts of what we'll probably use for our next-generation systems.

John's "The ultrahyperbolic Differential Equation with Four independent variables" Duke Math J, 1938, pp.300 - 322 gives the equation.

[+] Team 5: Network Analysis

**Mentor** Norm Curet, National Security Agency- Ariel Cintron-Arias, Cornell University
- Robert Ellis, University of California, San Diego
- Corey Gonzalez, University of Maryland
- Shobha Oruganti, Mississippi State University
- Patrick Quillen, University of Kentucky
- Lisa Rodriguez (Denogean), Cornell University

Network reliability analysis is a difficult computational problem that has attracted quite a bit of research at the interface of combinatorics, computer science and operations research. A central component of two-terminal reliability is the identification of minimum cutsets in a graph theoretic model of the underlying network. The idea is to calculate the probability that at least one path exists between some selected pair of terminal nodes through the identification of all cutsets in the corresponding graph. Since the exact calculations are intractable, bounds are calculated via identification of minimum weight cutsets.

This project will examine a network vulnerability variant of the two-terminal network reliability problem. Given a network with some small selected subset of "vulnerable" links, we would like to calculate the minimum number of network component failures that would have to occur so that all network communications involve at least one link in the vulnerable set. Students will have the opportunity to investigate several network flow models and propose combinatorial optimization algorithms based on lagrangean relaxation or other decomposition approaches. The end contribution will be to understand the mathematics behind these algorithms and to prototype one or more algorithms that can be deployed to analyze moderately sized networks in real-time.

**Textbook References:**

1. Michael Ball (editor), Network Models, Elsevier Amsterdam, 1995. (chapter on network reliability)

2. Rav Ahuja, James Orlin and Tom Magnanti, Network Flows, Prentice Hall New Jersey, 1993. (chapters on maximum flow and lagrangean relaxation)

3. Charles Colbourn, Combinatorics of Network Reliability, Oxford University Press, 1987 (Chapters 1 and 2)

4. George Nemhauser and Laurence Wolsey, Integer and Combinatorial Optimization, 1988 (Part I)

[+] Team 6: Design of a Microactuator

**Mentor** David Ross, Eastman Kodak Company- Yeojin Chung, University of California, Irvine
- Zsolt Lavicza, University of Cincinnati
- Hyeona Lim, Michigan State University
- David Malonza, Iowa State University
- Minsu Song, University of Illinois at Urbana-Champaign
- Nicoleta Tarfulea, The Pennsylvania State University

With advances in microelectronic device fabrication technology, it has become possible to make small mechanical devices on computer chips. Our problem will be to devise a model of such a device--a simple microactuator--and analyze it to optimize performance.

**References:**

Landau and Lifshitz, Theory of Elasticity, sections 12, 13, and 25.

The Feynman Lectures, Volume II, chapter 38.

Also, take a look at the website: http://www.mdl.sandia.gov/Micromachine/ in particular, look at the pictures and the movies.