By Darinka Dentcheva
The latest issue of SIAM Review contains two articles in the Education section. The first one is “Elementary Number Theory and Rader's FFT,” by Shlomo Engelberg. The article discusses how number theory makes the calculation of the discrete Fourier transform more efficient. The discrete Fourier transform converts a finite sequence of equally spaced samples of a function into another sequence of equally spaced observations of a complex-valued function in the frequency domain. The paper starts with an introduction to the Cooley-Tukey method of the fast Fourier transform (FFT), which can be called a divide-and-conquer algorithm. It uses a substantially smaller number of calculations in comparison to the straightforward definition-based computation. The construction of that method factorizes \(N\), the number of terms used to calculate each element in the sequence, i.e., the number of samples taken, and reformulates the summation using the factors. The Cooley-Tukey method works best if the number \(N\) is a power of 2. However, if one does not get to choose the number of samples, \(N\) might be a prime number, eliminating the advantage of the Cooley-Tukey method. In that case, another approach proves useful. It is based on the cyclic group of integer numbers modulo the number \(N\) (the given prime number of samples). Here the reader is reminded also about Fermat's little theorem, which is essential to establish the cyclic nature of the group. That approach carries the name of Rader. Further, the author brings to attention the occurrence of calculation intensity when working with particular prime numbers: Sophie Germain primes \(p\), which are such that \(2p+1\) are also primes. At the end of the article, several examples are discussed to illustrate how efficient the procedures really are. The authors have created a MATLAB code available for download.
The second article in the Education section is titled “Instability in Linear Cooperative Systems of Ordinary Differential Equations” and authored by Janusz Mierczyński. The author discusses stability of dynamical systems described by linear ODEs of the form \(x'=A(t)x\), where \(A(\cdot)\) is a matrix-valued function of time. The main focus is a method for constructing linear systems which are nonautonomous and are strongly cooperative: for each \(t \in \mathbb{R}\) the matrix \(A(t)\) has positive off-diagonal elements with a certain asymptotic behavior. The systems of interest have the real parts of all eigenvalues of \(A(t)\) negative and bounded away from zero, but nonetheless they have at least one (and frequently many) solutions whose magnitude grows to infinity with time.
Strongly cooperative dynamical systems are relevant mathematical models for some biological systems. The existence of solutions whose magnitude is bounded away from zero would indicate the survival of the population.
The first section of the paper surveys basic properties of autonomous linear systems which are described by a constant matrix \(A\) and an initial condition. The matrix \(e^{tA}\) is defined, and its role and actions are described. The author then goes on to show some spectral properties of matrices with positive off-diagonal elements. In particular, the principal eigenvalue of such a matrix is a strongly increasing function of any of its elements. Furthermore, it is shown (in the two-dimensional case) that the transition function of strongly cooperative systems is a matrix with all positive entries (Müller--Kamke theorem), and so is the matrix \(e^{tA}\). The author returns to the action of the latter matrix on the unit circle in order to provide insight into the behavior of nonautonomous systems. The main part of the paper discusses the construction of a nonautonomous (piecewise constant) planar linear system such that for each time \(t\), the larger eigenvalue of \(A(t)\) equals \(-\frac{1}{2}\), but the system has a solution not converging to zero at infinity. The author provides intuitive explanations, as well as in-depth analysis, pictures, and animations. In section 4, we find a discussion on how to construct systems with continuous or smooth matrix functions instead of piecewise constant ones. Finally, the author points out that the constructions could target quasi-periodic, almost periodic, and also more general time dependence (discussed in the penultimate section). The paper concludes with a discussion and ideas for project work: if random switching times were allowed, how would the systems need to be described in order to observe similar phenomena?
Darinka Dentcheva is a professor at the Department of Mathematical Sciences at the Stevens Institute of Technology. She is the section editor of the Education section of SIAM Review.