Scientific

Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

A general matrix A can be reduced to tridiagonal form by orthogonal
transformations on the left and right: UTAV = T. We can arrange that the
rst columns of U and V are proportional to given vectors b and c. An iterative
form of this process was given by Saunders, Simon, and Yip (SINUM 1988) and
used to solve square systems Ax = b and ATy = c simultaneously. (One of the
resulting solvers becomes MINRES when A is symmetric and b = c.)

The approach was rediscovered by Reichel and Ye (NLAA 2008) with emphasis
on rectangular A and least-squares problems Ax ~ b. The resulting solver was
regarded as a generalization of LSQR (although it doesn't become LSQR in
any special case). Careful choice of c was shown to improve convergence.

In his last year of life, Gene Golub became interested in \GLSQR" for
estimating cTx = bTy without computing x or y. Golub, Stoll, and Wathen
(ETNA 2008) revealed that the orthogonal tridiagonalization is equivalent to a
certain block Lanczos process. This reminds us of Golub, Luk, and Overton
(TOMS 1981): a block Lanczos approach to computing singular vectors.

On solving indefinite least squares problems via anti-triangular factorizations:
Nicola Mastronardi, IAC-CNR, Bari, Italy and Paul Van Dooren, UCL, Louvain-la-Neuve, Belgium

Communication-­ Avoiding Algorithms for Linear Algebra and Beyond

Convex Optimization for Finding Influential Nodes in Social Networks. Joint work with Lisa Elkin and Ting Kei Pong of Waterloo.