Comlab

(Joint work with Felipe Cucker and Dennis Cheung, City University of Hong Kong.)

\\

\\

Condition numbers are important complexity-theoretic tools to capture

a "distillation" of the input aspects of a computational problem that

determine the running time of algorithms for its solution and the

sensitivity of the computed output. The motivation for our work is the

desire to understand the average case behaviour of linear programming

algorithms for a large class of randomly generated input data in the

computational model of a machine that computes with real numbers. In

this model it is not known whether linear programming is polynomial

time solvable, or so-called "strongly polynomial". Closely related to

linear programming is the problem of either proving non-existence of

or finding an explicit example of a point in a polyhedral cone defined

in terms of certain input data. A natural condition number for this

computational problem was developed by Cheung and Cucker, and we analyse

its distributions under a rather general family of input distributions.

We distinguish random sampling of primal and dual constraints

respectively, two cases that necessitate completely different techniques

of analysis. We derive the exact exponents of the decay rates of the

distribution tails and prove various limit theorems of complexity

theoretic importance. An interesting result is that the existence of

the k-th moment of Cheung-Cucker's condition number depends only very

mildly on the distribution of the input data. Our results also form

the basis for a second paper in which we analyse the distributions of

Renegar's condition number for the randomly generated linear programming

problem.

Toeplitz matrices enjoy the dual virtues of ubiquity and beauty. We begin this talk by surveying some of the interesting spectral properties of such matrices, emphasizing the distinctions between infinite-dimensional Toeplitz matrices and the large-dimensional limit of the corresponding finite matrices. These basic results utilize the algebraic Toeplitz structure, but in many applications, one is forced to spoil this structure with some perturbations (e.g., by imposing boundary conditions upon a finite difference discretization of an initial-boundary value problem). How do such

perturbations affect the eigenvalues? This talk will address this question for "localized" perturbations, by which we mean perturbations that are restricted to a single entry, or a block of entries whose size remains fixed as the matrix dimension grows. One finds, for a broad class of matrices, that sufficiently small perturbations fail to alter the spectrum, though the spectrum is exponentially sensitive to other perturbations. For larger real single-entry

perturbations, one observes the perturbed eigenvalues trace out curves in the complex plane. We'll show a number of illustrations of this phenomenon for tridiagonal Toeplitz matrices.

\\

\\

This talk describes collaborative work with Albrecht Boettcher, Marko Lindner, and Viatcheslav Sokolov of TU Chemnitz.

We investigate the use of interior-point and semismooth methods for solving

quadratic programming problems with a small number of linear constraints,

where the quadratic term consists of a low-rank update to a positive

semi-definite matrix. Several formulations of the support vector machine

fit into this category. An interesting feature of these particular problems

is the volume of data, which can lead to quadratic programs with between 10

and 100 million variables and, if written explicitly, a dense $Q$ matrix.

Our codes are based on OOQP, an object-oriented interior-point code, with the

linear algebra specialized for the support vector machine application.

For the targeted massive problems, all of the data is stored out of core and

we overlap computation and I/O to reduce overhead. Results are reported for

several linear support vector machine formulations demonstrating that the

methods are reliable and scalable and comparing the two approaches.

Non-selfadjoint singular differential equation eigenproblems arise in a number of contexts, including scattering theory, the study of quantum-mechanical resonances, and hydrodynamic and magnetohydrodynamic stability theory.

\\

\\

It is well known that the spectra of non-selfadjoint operators can be pathologically sensitive to perturbation of the

operator. Wilkinson provides matrix examples in his classical text, while Trefethen has studied the phenomenon extensively through pseudospectra, which he argues are often of more physical relevance than the spectrum itself. E.B. Davies has studied the phenomenon particularly in the context of Sturm-Liouville operators and has shown that the eigenfunctions and associated functions of non-selfadjoint singular Sturm-Liouville operators may not even form a complete set in $L^2$.

\\

\\

In this work we ask the question: under what conditions can one expect the regularization process used for selfadjoint singular Sturm-Liouville operators to be successful for non-selfadjoint operators? The answer turns out to depend in part on the so-called Sims Classification of the problem. For Sims Case I the process is not guaranteed to work, and indeed Davies has very recently described the way in which spurious eigenvalues may be generated and converge to certain curves in the complex plane.

\\

\\

Using the Titchmarsh-Weyl theory we develop a very simple numerical procedure which can be used a-posteriori to distinguish genuine eigenvalues from spurious ones. Numerical results indicate that it is able to detect not only the spurious eigenvalues due to the regularization process, but also spurious eigenvalues due to the numerics on an already-regular problem. We present applications to quantum mechanical resonance calculations and to the Orr-Sommerfeld equation.

\\

\\

This work, in collaboration with B.M. Brown in Cardiff, has recently been generalized to Hamiltonian systems.

Stiff systems of ODEs arise commonly when solving PDEs by spectral methods,

so conventional explicit time-stepping methods require very small time steps.

The stiffness arises predominantly through the linear terms, and these

terms can be handled implicitly or exactly, permitting larger time steps.

This work develops and investigates a class of methods known as

'exponential time differencing'. These methods are shown to have a

number of advantages over the more well-known linearly implicit

methods and integrating factor methods.

The Kestrel interface for submitting optimization problems to the NEOS Server augments the established e-mail, socket, and web interfaces by enabling easy usage of remote solvers from a local modeling environment.

\\

\\

Problem generation, including the run-time detection of syntax errors, occurs on the local machine using any available modeling language facilities. Finding a solution to the problem takes place on a remote machine, with the result returned in the native modeling language format for further processing. A byproduct of the Kestrel interface is the ability to solve multiple problems generated by a modeling language in parallel.

\\

\\

This mechanism is used, for example, in the GAMS/AMPL solver available through the NEOS Server, which internally translates a submitted GAMS problem into AMPL. The resulting AMPL problem is then solved through the NEOS Server via the Kestrel interface. An advantage of this design is that the GAMS to AMPL translator does not need to be collocated with the AMPL solver used, removing restrictions on solver choice and reducing administrative costs.

\\

\\

This talk is joint work with Elizabeth Dolan.