Research

Shahadat Hossain Department of Mathematics and Computer Science University of Lethbridge

January 2, 2007

I am interested in mathematical optimization and its applications. The computational aspects of scientific problems that are largescale and display “exploitable” special properties such as sparsity and structural information such as symmetry are particularly intriguing. I find graph theory to be an important tool in exploiting the combinatorial structure inherent in many subproblems in nonlinear and linear optimization.

Current Research Activities.

My current research is concerned with the design of efficient algorithms for sparse matrix problems: efficient determination Jacobians and Hessians, linear algebra of Sparse matrices with special properties, and highperformance computing.

1. Efficient Algorithms for the Determination of Sparse Derivative Matrices.

(a)
A new graph model, the “pattern graph”, for sparse matrices that “preserves” the sparsity pattern of the underlying matrix while enabling columnoriented, roworiented, or combined vertex coloring problems without modifying the graph is described. This unified approach, in particular, is tremendously helpful in characterizing optimality criteria for different determination methods.

i. (With Trond Steihaug). Pattern Graphs for Sparse Matrices, Extended Abstract to appear in the proceedings of CSC 2007: The SIAM Workshop on Combinatorial Scientific Computing.

ii. (With Trond Steihaug). The CPR Method and Beyond – A Unified Approach, Submitted to IMA Journal of Numerical Analysis

(b)
An example due to Stanley Eisenstat shows shows that coloring the column intersection optimally does not necessarily correspond to optimal direct determination. The precise characterization of optimal determination of direct methods has only recently been proposed.

i. (With Trond Steihaug). Optimal Direct Determination of Sparse Jacobian Matrices, To appear in Optimization Methods and Software.

(c)
The first Integer Linear Program (ILP) for the bidirectional determination (bicoloring) problem as well as efficient implementation of some wellknown heuristics.

i. (With Mini Goyal). BiDirectional Determination of Sparse Jacobian Matrices: Approaches and Algorithms, Electronic Notes in Discrete Mathematics, Vol. 25, pp. 73–80, 2006.

(d)
A generalization of substitution (and elimination) methods utilizing zerononzero “patterns” in CPRcompressed Jacobian rows.

1

Shahadat Hossain Research

i. (With Trond Steihaug). Computing Sparse Jacobian Matrices Optimally, in Automatic Differentiation: Applications, Theory, and Implementations, Martin B¨

ucker, George Corliss, Paul Hovland, Uwe nauman, Bayona Norris (Eds.), Lecture Notes in Computational Science and Engineering, Vol. 50, Springer.

    1. Numerical Linear Algebra. The special structure of the Pascal seed matrices can be utilized to design efficient reconstruction algorithms. Some of these issues are discussed in the following short paper. A journal version of the paper includes the connection between the Pascal and Vandermonde systems and is forthcoming.

    2. (a) On Pascallike Matrices in Sparse Derivative Matrix Determination: Construction and Properties, in the proceedings of International Conference on Numerical Mathematics and Applied Mathematics, T.E. Simos, G. Psihoyios, Ch. Tsitouras (Eds), WILEYVCH, 2006.
  1. High performance Computing The gap between sustained and peak performance remains an important challenge for any HPC system doing sparse matrix computational kernels. We address the issue of efficient representation of sparse matrices.

(a) Issues in Optimizing Sparse Matrix Computational Kernels, IBM Center for Advanced Studies Conference, 2006.

(b) On Efficient Storage of Sparse Matrices, in the Proceedings of ICCSE, Hasan Dag, Yuefan Deng (Eds.), pp. 1–7.

Software. With undergraduate research student Zhenshuan Zhang I have developed code for graph coloring instance generator based on a given row partitioning of a sparse matrix.

  1. (With Trond Steihaug). Graph Coloring in the Estimation of Sparse Derivative Matrices: Instances and Applications, (To appear in Discrete Applied Mathematics).

  2. (With Zhenshuan Zheng). CsegGraph: Column Segment Graph Generator, (Submitted).

Graduate Students. Mini Goyal (M.Sc., graduated 2005), Minhaz F. Zibran (M.Sc. 2005

–)

Undergraduate Research Assistants. Meru Brunn, Zhenshuan Zhang, Matt Voronoi.

Research Grants. NSERC RGPIN (1999 – 2003, CAD 52,000), NSERC Discovery (2003 – 2008, CAD 65,000), UofL Startup(onetime), UofL Faculty Travel, ULRF, Dean of Arts and Science Research Grant(onetime).