Sardar Anisul Haque
Ph.D Student (Expected Graduation: June 2013)
The University of Western Ontario
Department of Computer Science
Middlesex College, Room No. MC327
London, Ontario, N6A 5B7
M.Sc. in Computer Science , December 2008
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,
Islamic University of Technology
- 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
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
- 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
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
- 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
- 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
- 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.
- Ontario Graduate Scholarship, 2012 - 2013.
- Queen Elizabeth II Graduate Scholarships 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.
Our poster at ISSAC, 2010 .
Slides of our presentation at SONAD, 2010 .
- Sardar Anisul Haque,
Marc Moreno Maza,
Determinant Computation on the GPU using the Condensation Method,
Journal of Physics: Conference Series. 341 012031.
- Sardar Anisul Haque,
Marc Moreno Maza,
Plain Polynomial Arithmetic on GPU,
Accepted for publication in Journal of Physics: Conference Series.
- Sardar Anisul Haque, and Shahadat Hossain ,
Marc Moreno Maza
Cache friendly Sparse Matrix-vector Multiplication,
Published in the Proceedings of the 4th International Workshop on Parallel and Symbolic Computation held in France, 2010, pp: 175-176 ACM.
- Sardar Anisul Haque, and Shahadat Hossain , A Note on the Performance of Sparse Matrix-vector Multiplication
with Column Reordering, Published in the proceedings of International Computing Conference held in Fullerton, California,
April 2-4, 2009.
- Solimul B. Chowdhury , Sakibul H.
, and Sardar Anisul Haque, Haplotype Inference by Pure Parsimony by SAT Solver
in Distributed Environment, International Journal of Computer Science and Network Security, Vol. 8 No. 8, pp. 247-254.
- Sardar Anisul Haque, A. B. M. Zohrul Kabir, and Ruhul Amin Sarker , Optimization Model for Opportunistic
Replacement Policy Using GA With Fuzzy Logic Controller, published in the proceeding of the IEEE Congress on Evolutionary
Computation, 2003 held on 10-12 December 2003 in Canberra, Australia, 2837-2843.
- Sardar Anisul Haque, M. Zahidul Hasan B., M. A. Mottalib, Tareque Mohmud Chowdhury, and Kazi Abu Baker Siddique,
Proposal for a Secured File System: Virtual Navigation File System, published in the proceedings of the conference
ICCIT-2004 held on 26-28 December 2004 at Brac University, Dhaka.
- Fazle Rabbi, Md. Shakhawat Hossain, Mainur Rahman, Sardar Anisul Haque, and M. A. Mottalib Particle Swarm Optimization with
Immune Technology(PSOIT): A New Hybridized Optimization Technique for Solving Multi-objective Optimization Problems,
published in the proceedings of the conference ICCIT-2005 held on 28-30 December 2005 at Dhaka, Bangladesh, pp. 75-80.
- Fazle Rabbi, Md. Shakhawat Hossain, Mainur Rahman, Sardar Anisul Haque, and and M. A. Mottalib A New Particle Optimizer Vaccinated
by Artificial Immune System (PSOVIS) for Constrained Nonlinear Optimization Problems, published in the proceedings of
the conference ICCIT-2005 held on 28-30 December 2005 at Dhaka, Bangladesh, pp. 34-39.
Last Updated: September 07,2012