Sardar Anisul Haque

Ph.D Student (Expected Graduation: June 2013)

Supervisor: Dr. Marc Moreno Maza

The University of Western Ontario
Department of Computer Science
Middlesex College, Room No. MC327
London, Ontario, N6A 5B7
E-Mail: shaque4@uwo.ca

• Academic Background
• Research Interests
• Recent Research Projects
• Major Awards
• Selected Publications
• Work Experience

Academic Background

M.Sc. in Computer Science , December 2008
Thesis Title: A Computational Study of Sparse Matrix Storage Schemes.
Thesis Supervisor: Dr. Shahadat Hossain
The University of Lethbridge
Lethbridge, Alberta, Canada

*I pursued a portion of my graduate studies at Concordia University, Montreal, Canada (January 2005 - August 2006). My main area of research was discovering new van der Waerden Numbers.

B.Sc. in Computer Science and Information Technology, October 2002
Islamic University of Technology
Gazipur, Bangladesh

Research Interests

• Algorithm and Data Structure Design for many-core architecture(GPU).
• Parallel Programming.
• High Performance Computing.
• Polynomial System Solving.
• Cache Complexity.
• Sorting Algorithms.
• Combinatorial algorithms.
• SAT solver.
• Large Scale optimization Problems.

Recent Research Projects

• Solving bivariate polynomial system solver on GPU.
  September 2012 to Present
  
  
• Fast evaluation of univariate polynomial over finite field on GPU using new data structure called "subinverse tree".
  January 2012 to August 2012
  Let our polynomial has degree less than n. Let the running time of multiplication process is M(n). We use a new data structure called subinverse tree in fast evaluation step. This improves the running time of the whole algorithm. In fact, we achieve the ratio between our running time and log(n)*M(n) as constant which is less than 4.02.
  
  
• Designed and developed parallel plain division and gcd on GPU.
  September 2011 to August 2012
  Both of the algorithms require linear parallel steps. In practice, a trivial GPU based implementation can not outperform other well known implementation (NTL or Maple). We found some intelligent ways to reduce the parallel steps by a linear factor. Our implementation outperform some well known fast implementations.
  
  
• Designed and developed parallel plain polynomial multiplication over finite field on GPU.
  January 2011 to December 2011
  Both FFT-based and plain polynomial multiplication have same parallel steps. Divide and conquer may not a suitable approach while designing parallel algorithm. Because it implies one more dependent step in multiplication phase. We can divide the solution space by drawing vertical lines. This way of partitioning give us a very fast polynomial multiplication that outperform FFT based multiplication until the degree is less than 2^13. Moreover this approach is very good for unbalanced polynomial.
  
  
• Computing determinant using condensation method on GPU
  March 2011 to August 2011
  
  
• Improving column permutation algorithm for improving cache complexity in sparse Matrix-vector Multiplication
  January 2010 to December 2010
  The cost for permuting columns/ rows of sparse matrix is too much to fit this as preprocessing steps in conjugate gradient type algorithm. The purpose of this preprocessing is to improve cache complexity in sparse Matrix-vector multiplication. We designed and developed a new algorithm to do this preprocessing which has linear time complexity. In other words the preprocessing cost is less than 100 sparse Matrix-vector multiplications.
  
  
• Implementation of ideal cache model
  May 2010 to June 2010
  
  
• Cache friendly counting sort algorithm
  January 2010 to February 2010
  This implementation is almost 3 times faster than the classical counting sort algorithm.
  
  
• Developed parallel algorithm for longest common subsequence problem using Cilk++
  January 2010 to March 2010
  
  
• Desigened and developed sorting algorithm for very big objects
  January 2010 to December 2010
  The comparison based sorting algorithm has complexity O(nlog(n)) if the objects are in machine words. Otherwise, the cost is multiplied by the cost of comparison function. Is there any way to sort very big objects within this time bound? We designed and developed algorithm which can sort big objects in less than O(nlog(n)).
  
  
• Sparse Matrix-vector Multiplication
  September 2007 to December 2008
  We designed a binary reflected Grey code based reordering of columns that improves the data locality of sparse matrices.
  
  
• Implementations of DPLL Algorithm
  January 2005 to December 2005
  Implementation of DPLL algorithm with some well known branching rules and one new branching rule based on estimation theory.
  
  
• Computing Van der Waerden number(2; 5, 6).
  May 2006 to April 2007
  It is found as 206.
  
  

Major Awards

• Ontario Graduate Scholarship, 2012 - 2013.
• Queen Elizabeth II Graduate Scholarshi​ps in Science and Technology, 2011 - 2012.
• The University of Western Ontario Biocomputing Student Award, May 2009.
• International Graduate Research Scholarship, 2007 - 2008.
• "David J. Azrieli Graduate Fellowship (September 2005 - April 2006)", by the School of Graduate Studies of Concordia University, Montreal, Canada. This fellowship is awarded to the top ranked graduate student.

Presentation