We can categorically state that we have not released man-eating badgers into the area

, BBC News 2007

S.B. Stečkin (С.Б. Стечкину)

$\newcommand{\complex}{\mathbf{C}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\maxmod}[1]{\norm{#1}_\infty}$

S.B. Stečkin's lemma concerns behaviour of a trigonometric polynomial near its maximum. To be precise, if the polynomial $$f(t) = \sum_{\abs{n}\leq N}\alpha_{n}e^{int} \quad (\alpha_{n}\in\complex)$$ is real-valued and $t_{0}\in [0,2\pi]$ satisfies $f(t_{0})=\maxmod{f} = \max\left\{\abs{f(t)}\;:\; t\in [0,2\pi]\right\}$, then $$f(t_{0}+s) \geq \maxmod{f}\cos Ns \quad (\abs{s}\leq \pi/N).$$ In other words, the polynomial decays no faster that $\cos Ns$ close to a maximum without any reference to derivatives. This lemma and its generalisations can be used to construct “subdivide and reject” algorithms for global optimisation of non-convex objectives.

## maxmod

The maxmod algorithm calculates the maximum modulus of a complex polynomial on the unit disc using a method of repeated subdivision of $[0,2\pi]$ and rejection of non-maximizing subintervals. A detailed description of the algorithm and its performance can be found here.

The algorithm was used by Gregory Janks in a numerical demonstration that the Mandelbrot set is locally connected at the Feigenbaum point.

## maxmodnd

Gabriel De La Chevrotière (McGill University) has generalised Stečkin's lemma to the multivariate case and so derives a method for finding the maximum modulus of a multivariate polynomial on the polydisc. The paper, published in SIURO, can be downloaded here.

## opnorm

Threading performance of opnorm for matrices of order $n \times n$, on a dual Intel Xeon 2.80 GHz with hyperthreading enabled (4 virtual CPUs). Timings are in milliseconds for a (4,4)-norm averaged over 128 random (Gaussian) matrices.
order 1 2 3 4
2 0.349 0.337 0.348 0.381
3 1.326 1.029 1.052 1.077
4 8.483 6.126 5.953 5.767
5 62.391 41.018 36.628 35.747
6 474.887 293.007 247.254 219.428
7 3605.859 2143.565 1776.399 1566.617

S.W. Drury (McGill University) has proved a Stečkin-like estimate for operators from finite dimensional real vector spaces with the $p$-norm to Banach spaces with easily computed norms. This enables him to implement the first general algorithm for calculating the $\ell_p \rightarrow \ell_q$ operator-norms of matrices (albeit those with a small number of columns), and so allows him to find a counterexample to a long-standing conjecture of Matsaev.

• S.W. Drury's paper in Linear Algebra and its Applications (subscription required) and his webpage on the algorithm, including implementations for Visual C++ and Maple.
• The opnorm package, a multi-threaded C99 implementation targeted at Unix-like systems with bindings for Matlab, Octave and Python.
• As can be seen from the table right, the algorithm appears to require time which is exponential in the order of the matrix (in fact in the number of columns), so that only matrices with fewer that 10 columns are feasible. But this is to be expected, since Julien M. Hendrickx and Alex Olshevsky have shown (arXiv) that the problem is NP-hard.

17/05/2013

lang en fr | validate xhtml css