Why Solve the Eigen Problem?

Posted 11-07-2008

This podcast and transcript is intended for students taking MATH353. Bob Broughton introduces the eigen problem, the diverse areas where it occurs and the motivations for solving it.

Download

References and further reading mentioned in the podcast are listed in the references section and are indicated in by a pluck of a string. The transcript also shows the references in context.

Transcript

Introduction and motivation

In most linear algebra texts the eigen problem is presented as a mathematical matrix/vector equation. Whereas the similar equation representing a system of linear equations is instantly clear in its derivation, the eigen equation appears as if a rabbit from a hat with no rationale for its being. Often the response from mathematicians is that the eigenvalue is the stretch (or reduction) in the length of a vector under a matrix transformation. This doesn’t really answer the question posed. However if the solution of systems of first order linear ordinary differential equations is investigated through the solution of a single linear differential equation it will be shown that the eigen equation is a natural consequence. Such systems are concerned with rates of growth and decay which are examples of eigenvalues.

Furthermore in the course on ordinary differential equations it is seen that second order differential equations often lead to oscillating solutions by virtue of complex growth rates. Such solutions involve frequencies of oscillation and these are directly related to eigenvalues. Our environment is full of things that vibrate, and subject to systems that grow or decay. In other words we live in an eigen world.

The human race has made gigantic leaps forward in science, technology, engineering, economics, and medicine in the past century and the ability to solve eigen problems has been part of this advancement. This article looks at the diverse areas where the eigen problem occurs. So let us start with a passage from Zhaojun Bai and Chao Yang [1]:

… What is common among electronic structure calculation, design of MEMS devices, vibrational analysis of high speed railways, and simulation of the electromagnetic field of a particle accelerator? The answer: they all require solving large scale nonlinear eigenvalue problems. In fact, these are just a handful of examples in which solving nonlinear eigenvalue problems accurately and efficiently is becoming increasingly important. …

Another view of eigen problems comes from Yeliang Zhang and co. [2]:

… The computation of eigenvalues and eigenvectors is an important and often time-consuming phase in computer simulations. Without being exhaustive, eigenvalues and eigenvectors are used in the study of nuclear reactor dynamics (stability of neutron fluxes [3]), in finite element dynamic analysis of structural models (e.g., seismic simulations of civil infrastructure [4], [5]), in the design of the next generation of particle accelerators [6], in the definition of a set of eigenfaces in biometric-based identification systems [7], in the solution of Schrodinger’s equation in chemistry and physics [8], in the design of microelectromechanical systems (MEMS) [9], [10], and in the study of conformational changes of proteins [11]. Because of the need for higher levels of simulation details and accuracy, the size and complexity of the computations grow as fast as the advancement of the computer hardware. In order to cope with the increasing need of solving eigenvalue problems, various useful numerical algorithms that are suitable for solving large-scale eigenvalue problems are developed. Some of these numerical libraries also have parallel implementations [12], [13], [14], [15]. With the growing availability of solvers scientists are no longer facing the problem of no available algorithms to use but too many algorithms to choose from. However, little consideration is given to provide a robust and effective way to sift out a best solver for a particular application. For sequential or parallel algorithms, a suitable choice of solver may have an impact of order of magnitude on an application compared to a bad one. …

Other areas involving eigen problems are in communications and networks. In order to improve performance in data transmission and reception on wireless devices research is being conducted on MIMO systems. MIMO stands for Multiple Input, Multiple Output and involves using multiple antennae on the transmit and/or receive end to boost data rates or improve RF signal performance. For example cell phone systems have been single input/output and MIMO systems are being implemented to improve existing transmitter-receiver systems. In the mathematics of networks, matrices represent the connections between vertices. These matrices are often very large but also extremely sparse in structure. Such matrices occur in modern real world networks such the Internet and web data, biological, and social networks. For searching the web, Google involves a matrix of order 2.7 billion and the PageRank algorithm is an eigen problem solver [16], [17], [18].

Eigenvalues, Eigenvectors, Eigenfunctions

The mathematics of the eigen problem are relatively recent but the real-world knowledge of the concepts have been known for a lot longer. Indeed Joshua presumably knew about resonance when he fought the battle of Jericho and the walls came tumbling down, as a result of blowing on large horns and trumpets. Earthquakes have destroyed buildings for centuries, in Roman times soldiers broke step crossing bridges, and in music, musicians tune their instruments by matching frequencies. The idea of talking to one another using a string stretched tightly between two cans has been tried by children and those young at heart. The vibrations in the voice will transfer to the string. Basically a string that you strike will vibrate and that will produce tones and overtones. The oscillating shape that a specific vibrating string takes and the associated pitch of the tone are characteristic (eigen in German) to the string. These depend on the length and cross-section of the string, on the material of which the string is composed and on the tension on the string. Hence the natural shape of the vibrations and the natural pitch of the tones are termed natural or eigen modes, or eigenvibrations, and natural or eigen frequencies, respectively. In mathematics these are referred to as eigenfunctions and eigenvalues. Every structure from strings and musical instruments, to buildings, bridges, vehicles, planes, and oceans, has its own system of eigenvibrations and eigenfrequencies. The eigenfunctions associated with strings are simple (sines) and are called harmonic oscillations. If we were to consider the displacements of the string at discrete points then we would have a vector of values, the eigenvector.

It is fairly easy to let a string vibrate without striking it: a string will start vibrating as soon as you hit another nearby string that has been tuned to the same frequency. This phenomenon is called resonance and it does not only occur with music instruments. Wind can possibly have a still more dramatic impact on a bridge (The Tacoma Bridge collapse, [19], [20], [21]).

Important for New Zealand is the effect of earthquakes on buildings which has led to the University of Canterbury being world leaders in designing earthquake-proof buildings. This is a problem for many other countries as well of course, and the issue here is to design structures that won't resonate with the induced frequencies.

Many of these factors come into the design of structures such as bridges. In recent years very large bridges have been constructed. For example the Akashi Kaikyo Bridge in Japan, which stretches 3916m across the Akashi Strait to link the city of Kobe with Awaji-shima Island. It would take four Brooklyn Bridges to span the same distance! The Akashi Kaikyo Bridge is also extremely tall with two towers soaring 285m, [22].

Engineers had to consider the weather. Japan experiences some of the worst weather on the planet. Gale winds whip through the Strait. Rain pours down at a rate of 145cm per year. Hurricanes, and earthquakes rattle and thrash the island almost annually. As part of the solution engineers placed 20 tuned mass dampers (TMDs) in each tower.

More and more of these very large bridges are being built, [23].

We have considered sources of vibration and resonance from earthquakes and wind, but there have been problems with bridges caused by mechanical human sources. The now infamous Millennium Pedestrian Bridge in London which swayed badly when opened to pedestrians required mass dampers, [24]. This and other examples including the problems of marchers on the Auckland Harbour bridge are discussed by David Newland from Cambridge University and Blekherman [25], [26] in their papers. Tuned mass dampers have been used to counteract the swaying of tall buildings as well as in bridges, [27].

In this article applications of TMDs to vehicles are also discussed. Vibration in vehicles is of major concern since resonance in aircraft would spell disaster. On the other hand brake noise and vibration issues in the automotive industry costs approximately $1 Billion/year in Detroit alone, [28]

  • Frequencies are also used in electrical systems. When you tune your radio, you are changing the resonant frequency until it matches the frequency at which your station is broadcasting.

  • Eigenvalues can also be used to test for cracks or deformities in a solid and oil companies frequently use eigenvalue analysis to explore land for oil.

  • Frequencies are also vital in music performance. When instruments are tuned, their frequencies are matched. It is the frequency that determines what we hear as music. Although musicians do not study eigenvalues in order to play their instruments better, the study of eigenvalues can explain why certain sounds are pleasant to the ear while others sound “flat” or “sharp”. When two people sing in harmony, the frequency of one voice is a constant multiple of the other. Eigenvalues can be used to explain many aspects of music from the initial design of the instrument to tuning and harmony during a performance. Even the concert halls are analyzed so that every seat in the theater receives a high quality sound.

  • Eigenvalue analysis is also used in the design of car stereo systems so that the sounds are directed correctly for the listening pleasure of the passengers and driver. Think of eigenvalues next time you experience the passing of a throbbing boombox.

Many of the applications can be recognised as long standing but the list of applications is growing as new applications arise such as in MIMO and MEMS.

Recent years have seen the rise of MEMS systems which are generally of very small (millimeter down to micrometer) and involve finite element analysis.

Common applications include:

  • inkjet printers, which use piezoelectrics or bubble ejection to deposit ink on paper.

  • accelerometers in modern cars used for a large number of purposes including airbag deployment in collisions.

  • MEMS gyroscopes used in modern cars and other applications to detect yaw; for example to deploy a roll over bar or trigger dynamic stability control.

  • pressure sensors; for example car tire pressure sensors, and disposable blood pressure sensors.

  • Displays; for example the DMD chip in a projector based on DLP technology has on its surface several hundred thousand micromirrors which is great for large screens.

  • Optical switching technology which is used for switching technology and alignment for data communications, and is part of the emerging technology of smartdust.

Also check out David Bindel's website at UC Berkeley, [29], [30].

Eigenvalues are very much part of problems involving growth and decay such as population problems both in terms of species and biological areas such as cells (cancer) and bacteria, spread of disease, predator-prey problems, chemical reactions, and problems in commerce and economics.

Eigenvalues play a central role in uncoupling structures into principle components. For example in statistics in factor analysis relating to covariance matrices. Factor analysis is a statistical technique used in the social sciences and in marketing, product management, operations research, and areas that similarly deal with large quantities of data.

You will have come across uncoupling processes in second year courses with respect to solving systems of first order ordinary differential equations by diagonalization, and expressing geometric quadratic forms in normal form. Again the concept of characteristic, natural or normal modes appears.

Growth/decay aspects of the eigen problem are related to the concept of stability. This is particularly important in numerical mathematics where we are concerned with numerical stability with regard to the behaviour of errors. Eigen values determine whether floating point error grows in an unstable manner to such an extent that the true solution is swamped, or whether a method is stable with respect to floating point error. Stability analysis determines whether or not a numerical process is acceptable as a solver.

One of the common threads in eigen problems is that there is a need to solve larger and larger problems. As applications change due to the ability to solve larger and larger problems arising from structures or networks of increasing size there is a need to produce eigen solvers that will deal effectively with these problems. The ability to solve increasingly large problems has gone hand in hand with developments in computer technology.

The aim of this course is to give a basic mathematical background in the matrix algebra of the eigen problem backed up by the themes and fundamentals of major algorithms. MATLAB is used in the course to both enhance skills in computational matrix algebra and to implement algorithms in order to reinforce understanding of the processes involved.

References

  1. Zhaojun Bai and Chao Yang, From Self Consistency to SOAR: Solving Large Scale Nonlinear Eigenvalue Problems SIAM News, Volume 39, Number 3, April 2006
  2. Yeliang Zhang, Xiaoye S. Li, Osni Marques Towards an Automatic and Application-Based Eigensolver Selection
  3. G. Verdu, D. Ginestar, V. Vidal, and J. L. Munoz Cobo. 3D - λ Modes of the Neutron-Diffusion Equation, Ann. Nucl. Energy, 21:405421, 1994.
  4. F. Y. Cheng, Matrix Analysis of Structural Dynamics: Applications and Earthquake Engineering, Marcel Dekker, New York, N.Y., 2000.
  5. A. K. Chopra, Dynamics of Structures: Theory and Applications to Earthquake Engineering, Prentice Hall, Upper Saddle River, N.J., 2nd edition, 2000.
  6. K. Ko, N. Folwell, L. Ge, A. Guetz, V. Ivanov, L. Lee, Z. Li, I. Malik, W. Mi, C. Ng, and M. Wolf, Electromagnetic systems simulation -from simulation to fabrication, SciDAC Report, 2003. Menlo Park, CA.
  7. M. Turk and A. Pentland, Eigenfaces for Recognition, Technical report, Vision and Modeling Group, The Media Laboratory, MIT, 1990.
  8. M. Payne, M. P. Teter, D. C. Allan, T. A. Arias, and J.D. Joannopoulos, Iterative minimization techniques for ab initio total energy calculations: Molecular dynamics and conjugate gradients, Rev. Mod. Phys., 1045, 1992.
  9. J. V. Clark, D. Bindel, N. Zhou, S. Bhave, , Z. Bai, J. Demmel, and K. S. J. Pister, SUGAR: Advancements in a 3D multi-domain simulation package for MEMS, In Proceedings of the Microscale Systems: Mechanics and Measurements Symposium, Portland, OR, June 4 2001.
  10. M. ArikV, S. M. Zurnx, A. Bar-CohenV, Y. Namx, D. Markusx, and D. Pollax Development of CAD Model for MEMS Micropumps, Laboratory for Thermal Management of Electronics, Department of Mechanical Engineering, Microtechnology Laboratory, Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55414
  11. O. A. Marques and Y.-H. Sanejouand, Hinge-Bending Motion in Citrate Syntase Arising from Normal Modes Calculations, Proteins: Structure, Function and Genetics, 23:557560, 1995.
  12. L. S. Blackford, J. Choi, E. DAzevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley, ScaLAPACK Users Guide, SIAM, Philadelphia, 1997.
  13. Rich Lehoucq, Kristi Maschhoff, Denny Sorensen, and Chao Yang, Parallel ARPACK.
  14. O. A. Marques, BLZPACK: Description and Users Guide, Technical Report TR/PA/95/30, CERFACS, Toulouse, France, 1995.
  15. Kesheng Wu and Horst Simon, Thick-restart lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Analysis and Applications, 22(2):602616, 2001.
  16. Cleve Moler, The World's Largest Matrix Computation, Cleve's Corner, The MathWorks MATLAB News & Notes October 2002.
  17. Google, Google searches moe sites more quickly, delivering the most relevant results, 2007
  18. Amy N. Langville and Carl D. Meyer, Google's PageRank and Beyond: The Science of SEARCH ENGINE RANKINGS, Princeton University Press, 2006.
  19. Ivars Peterson, Rock and Roll Bridge
  20. Stuart Doole and Alan Champneys, Tacoma Narrows Bridge Disaster.
  21. Eigenvalue problems, University of Utrecht.
  22. Akashi Kaikyo Bridge, Wonders of the World databank, PBS.
  23. List of longest suspension bridge spans, Wikipedia.
  24. P. Dallard, A. J. Fitzpatrick, A. Flint, S. Le Bourva, A. Low, R.M. Ridsdill Smith, M. Willford, The London Millennium Footbridge The Structural Engineer Volume 79/No 22 20 November 2001
  25. David E. Newland, Pedestrian Excitation of Bridges - Recent Results, 10th International Conference on Sound and Vibration, Stockholm, Sweden, 2003.
  26. Alexander N. Blekherman, Swaying of Pedestrian Bridges, Journal of Bridge Engineering, March/April 2005.
  27. Tuned mass damper, Wikipedia
  28. Himanshu Misha, Wayne Nack, Tom Kowalski, Louis Komzsik, and Erwin Johnson, Brake Analysis and NVH Optimization Using MSC.NASTRAN.
  29. Microelectromechanical systems, Wikipedia
  30. Sandia National Laboratories Silicon-Based MEMS, Sandia National Laboratories.