aerial-sfu

Welcome to the Office of Graduate Studies & Postdoctoral Fellows

Future Students

Our internationally recognized graduate programs will expand your intellectual horizons, strengthen your skill set and enhance your professional network.

Current Students

We are here to help you complete your graduate program and acquire the necessary skills for success after graduation.

Student's researching

Upcoming Events

  • LEVISOHN-Schiphorst PhD Dissertation SIAT
    8:00 AM - 12:00 PM
    November 24, 2014
    Aaron LEVISOHN PhD Candidate SIAT Title Abstract Examining Committee Chair Lyn Bartram Senior Supervisor Thecla Schiphorst Supervisor Alissa Antle Supervisor Cheryl Prophet, SCA, SFU Internal Examiner Tom Calvert External Examiner Kristina Hook, Sweden, Mobile Life
  • Nathan Sharp, M.Sc. Thesis Defence, Mathematics
    2:30 PM - 4:30 PM
    November 24, 2014
    (Sr. Supervisor: Manfred Trummer) Title: Barycentric Rational Interpolation and Spectral Methods Abstract: Spectral methods typically give excellent accuracy with relatively few points (small N), but certain numerical issues arise with larger N. This thesis focuses on spectral collocation methods, also known as pseudo-spectral methods, that rely on interpolation at collocation points. A relatively new class of interpolants will be considered, namely the Floater-Hormann family of rational interpolants. These interpolants and their properties will be studied, including their use in differentiation by means of differentiation matrices based on rational interpolants in the barycentric form. Then, consideration will be given to the solution of singularly perturbed boundary value problems though the use of boundary layer resolving coordinate transformations. Finally, coupled systems of singularly perturbed boundary value problems will be investigated, though only with the standard Chebyshev collocation method.
  • Piyashat Sripratak, Ph.D. Thesis Defence, Mathematics
    10:00 AM - 12:00 PM
    November 25, 2014
    (Sr. Supervisor: Abraham Punnen) (Co-Supervisor: Tamon Stephen) Title: The Bipartite Boolean Quadratic Programming Problem Abstract: We consider the Bipartite Boolean Quadratic Programming Problem (BQP01), which generalizes the well-known Boolean quadratic programming problem (QP01). The model has applications in graph theory, matrix factorization, bioinformatics, among others. BQP01 is NP-hard. The primary focus of the thesis is on studying algorithms and polyhedral structure from a linearization of its integer programming formulation. We show that when the rank of the associated m x n cost matrix Q is fixed, BQP01 can be solved in polynomial time. In contrast, the corresponding QP01 version remains NP-hard even if Q is of rank one. Further, for the rank one case, we provide an O(n log n) algorithm. The complexity reduces to O(n) with additional assumptions. Further, we observe that BQP01 is polynomially solvable if m=O(log n) but NP-hard if m=O(sqrt n). Similarly, when the minimum negative eliminator of Q is of O(log n), the problem is shown to be polynomially solvable but remains NP-hard if this parameter is O(sqrt n). We then develop several heuristic algorithms for BQP01 and analyze them using domination analysis. First, we give a closed-form formula for the average objective function value A(Q,c,d) of all solutions. Computing the median objective value however is shown to be NP-hard. We prove that any solution with objective function value no worse than A(Q,c,d) dominates at least 2{m+n-2} solutions and provide an upper bound for the dominance ratio of any polynomial time approximation algorithms for BQP01. Further, we show that some powerful local search algorithms could produce solutions with objective value worse than A(Q,c,d) and propose algorithms that guarantee a solution with objective value no worse than A(Q,c,d). Finally, we study the structure of the polytope BQP{m,n} resulting from linearization of BQP01. We develop various approaches to obtain families of valid inequalities and facet-defining inequalities of BQP{m,n} from those of other related polytopes. These approaches include rounding coefficients, using the linear transformation between BQP{m,n} and the corresponding cut polytope, another polytope closely related to QPn and BQP{m,n} and applying triangular elimination, a technique developed for obtaining valid inequalities for a cut polytope from another cut polytope with different underlying graph.
  • Download .ics