Scientific Computing Seminar

Date:
Tuesday, February 21, 2006
Time:
11:00am-12:00pm
Location:
50A-5132
Seminar Speaker:
Makoto Yamshita
Shindoh Lab
Department of Industrial Engineering and Management
Kanagawa University, Japan
http://www.shin.ie.kanagawa-u.ac.jp/~makoto/
Title:
Parallel Computation for Numerical Optimization: Polynomial Equations and SemiDefinite Programming
Abstract:
In recent years, achievements in parallel computation have received increasing attention in the field of numerical optimization. In this talk, we introduce two examples of parallel computation applied to numerical optimization problems: Polynomial Equations and SemiDefinite Programming.

Enumerating all isolated solutions of a system of polynomial equations arises from, for example kinematics of a robot arm and a geometric intersection computation. The polyhedral homotopy continuation method numerically traces paths from solutions of a reduced simple system to solutions of the original system. Although the number of paths becomes more than a million, each path can be traced independently. We execute the homotopy method on grid computing environment with the Ninf-G library built upon the Globus system and obtain all these millions of isolated solutions.

SemiDefinite Programming comprises the optimization of a linear objective function with a linear matrix inequality constraint. Most of the computation time of Primal-Dual Interior-Point Methods for SDPs is occupied by a computation of the so-called Schur complement matrix involved in a modified Newton method. To dissolve the bottlenecks, we implement parallel software using MPI and Scalapack. Numerical results show that the software successfully reduces the total computation time. In addition, we introduce an online version of the parallel software, which enables users without a parallel computation environment to solve their SDPs via the Internet.

Sponsor of Seminar:
Zhengji Zhao
Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov