Saturday, March 17, 2012

Can a region of absolute stability be rectangular?

When a one-step integrator is applied to the solution of the linear scalar ODE

$$u'(t) = \lambda u(t)$$

the resulting iteration takes the simple form

$$U^{n} = R(h\lambda) U^{n-1}$$

where $U^n$ is a numerical approximation to the solution $u(t_n)$ and $R(h\lambda)$ is called the stability function.  The details of the stability function depend on the choice of numerical method, but for any explicit Runge-Kutta method, $R(z)$ is a polynomial whose degree is at most the number of stages of the method.

The stability function completely characterizes the accuracy and stability of the method when applied to linear problems.  Consider the first order linear, autonomous ODE

$$u'(t) = L u(t)$$

where now $u$ is a vector and $L$ is a square matrix.  The numerical solution will be

$$U^{n} = R(hL) U^{n-1}.$$

The global error satisfies a similar recurrence; in particular, it gets multiplied by a factor $R(hL)$ at each step.  Let $\lambda$ denote any eigenvalue of $L$; then If $L$ is a normal matrix, the solution will be absolutely stable in the Euclidean norm if all values $h\lambda$ lie within the stability region $S$, defined as

$$S = \{ z\in\mathbb{C} : |R(z)|\le 1\}.$$

Thus the region of absolute stability defines the portion of the complex plane in which a given numerical integration method may appropriately be applied.

In our preprint on Runge-Kutta stability regions, Aron Ahmadia and I claim that we have an algorithm to generate a stability region appropriate for any spectrum.  By considering high-degree polynomials, we find that the resulting stability regions are tightly adapted to the shape of the imposed spectrum.

While this promises to be very useful for some problems, it also has an aspect that's just fun: we can generate stability regions with unusual shapes.  I haven't explored this much yet, but a first question that we ask in the preprint is how to generate a stability region for a spectrum of eigenvalues forming a rectangle in the left half of the complex plane.

Here is an example of a resulting stability region:


The gray region is the set $S$ for a certain degree-20 stability polynomial corresponding to a consistent twenty-stage Runge-Kutta method.  As one colleague told me when I showed it to him, "this seems too good to be true; is that rectangle really the stability region?"

Indeed it is.  Zooming in on the top edge we see the detailed structure of the boundary:


Zooming in even closer:


As is typical with optimal stability polynomials, we se that the boundary is tangent or nearly tangent to the desired region at a large number of points (about 20 in this case).

What other shapes can be approximated?  More on that later...

Tuesday, March 13, 2012

Should your advisor be an author on your papers?

Authorship seems to be a complicated business in science.  What is required to qualify for authorship?  The first time I gave my thesis advisor a draft with his name on it, he politely told me that he liked it very much but it wasn't necessary to include him as an author since the research and writing had been done by me (this even despite the fact that the original idea for the project was his).  In the end, he became more closely involved in some of the work and the revision of the paper, and we agreed that he should be an author.  But that experience reinforced for me the high threshold for authorship that is usually expected in mathematics.
I was surprised to find that the "accepted" answer to this question on
What are the requirements for a supervisor to be included as an author on a paper, as opposed to just appearing in the acknowledgements?
As a graduate student, you can expect that your advisor will appear as an author on all of your papers.  He is providing your funding, your resources, and (ostensibly) is the Primary Investigator on whatever project you happen to be working on. Even if he does not contribute, you are working on his project, and he wrote the grant for it, not you.
I was relieved to see that the currently highest-voted answer (though by a narrow margin) states
In theoretical computer science (and mathematics), it is generally considered unethical to list someone as a co-author who has not made a novel and significant intellectual contribution to the paper. In particular, merely funding the research is not considered an intellectual contribution. Adding a supervisor's name to a paper to which they have not directly, intellectually contributed is lying.
Clearly, the difference in perspective is based on different understandings of what authorship means.  However, it seems clear that one cannot be an author of a document that one did not write any part of.  And apparently KAUST's administration agrees with me on that count; in KAUST's "Code of Practice on Responsible Conduct of Research", one finds the following:
...the practice of gift or honorary authorship (that is the listing as an author by virtue of their reputation or seniority, e.g. as head of the laboratory, of someone who does not qualify as an author) [is] unacceptable.
And furthermore
The list of authors should be limited to those researchers who have made a substantial and identifiable intellectual contribution to the research upon which a publication is based.
At mathoverflow, more interesting answers are given, including this highly-voted point of view: a rule the supervisor should not be a co-author in the main paper taken from a student's thesis, even if he has contributed substantially to it...
and this one, which aligns with my own perspective:
...if I suggest a problem and react to discussions with a student by giving suggestions and helping with background and helping with proofs, then I will not be a co-author.  If I do work by myself on the paper, doing important technical work, then I must be a co-author.