Curriculum Vitae

Arne Storjohann

Citizenship: German (Canadian permanent resident)

Languages: English, German

Present position: Associate Professor at the David R. Cheriton the School of Computer Science, University of Waterloo, Canada, September 2002 -- present

Education, Employment:

2001--2002

Postdoc at the Ontario Research Center for Computer Algebra

2000

Ph.D. from the Swiss Federal Institute of Technology, ETH-Zurich, Switzerland
Dissertation Title: "Algorithms for matrix canonical forms."
Advisor: Prof. Dr. Gaston Gonnet

1995

Research Assistant, Symbolic Computation Group, University of Waterloo

1994

M.Math. in Computer Science at the University of Waterloo, Canada
Thesis Title: "Computation of Hermite and Smith normal forms of matrices."
Advisor: Prof. Dr. George Labahn

1992

B.Math. at the University of Waterloo

Awards:

2007

Early Researcher Award, from the Government of Ontario, for demonstrated excellence in scientific and academic contributions.

2004

NSERC Synergy Award for Innovation, jointly with K. Geddes, M. Giesbrecht and G. Labahn as part of the Symbolic Computation Group, University of Waterloo.

2003

Distinguished Paper, at the International Symposium on Symbolic and Algebraic Computation: ISSAC '02, held in Lille, France. Award announced at ISSAC'03.
Title: "High-order lifting."

1999

Best Research Paper, with Thom Mulders, at the International Symposium on Symbolic and Algebraic Computation: ISSAC '99, held in Vancouver, British Columbia.
Title: "Diophantine linear system solving."

Refereed Journal Papers:

• A. Storjohann. On the complexity of inverting integer and polynomial matrices. To appear in Computational Complexity.
• Z. Chen and A. Storjohann. Lattice compression of integer matrices. To appear in the Journal of Symbolic Computation.
• A. Storjohann. The modulo extended gcd problem and space efficient algorithms for integer matrices. To appear in Journal of Algorithms.
• A. Storjohann. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, 21(4):609-650, 2005.
• T. Mulders and A. Storjohann. Certified dense linear system solving. Journal of Symbolic Computation, 37(4):485-510, 2004.
• D. Saunders, A. Storjohann, and G. Villard. Matrix rank certification. Electronic Journal of Linear Algebra, 11:16-23, 2004.
• A. Storjohann. High-order lifting and integrality certification. Journal of Symbolic Computation, 36(3-4):613-648. 2003.
• T. Mulders and A. Storjohann. On lattice reduction for polynomial matrices. Journal of Symbolic Computation, 35(4):377-401, 2003.
• M. Giesbrecht and A. Storjohann. Computing rational forms of integer matrices. Journal of Symbolic Computation, 34(3):157-172, 2002.
• A. Storjohann. Computing Hermite and Smith normal forms of triangular integer matrices. Linear Algebra and its Applications, 282:25-45, 1998.
• A. Storjohann and G. Labahn. A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix. Linear Algebra and its Applications, 253:155--173, 1997.

Refereed Conference Proceedings Papers:

• A. Storjohann. Integer matrix rank certification. In J.P. May, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '09, pages 333-340, 2009. ACM Press.
• C. Pernet and A. Storjohann. Faster algorithms for the characteristic polynomial. To appear in Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '07, 2007. ACM Press.
• W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard. Faster inversion and other black box matrix computations using efficient block projections. To appear in Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '07, 2007. ACM Press.
• Z. Olesh and A. Storjohann. The vector rational function reconstruction problem. In I. Kotsireas and E.V. Zima, editors, Proc. of the Waterloo Workshop on Computer Algebra: devoted to the 60th birthday of Sergei Abramov (WWCA), World Scientific, 2006, pages 137-149.
• W. Eberly, M. Giesbrecht, P. Giorgi and A. Storjohann. Solving sparse rational linear systems. In J.-G. Dumas, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '06. ACM Press.
• Z. Chen and A. Storjohann. A BLAS based C library for exact linear algebra on integer matrices. In M. Kauers, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '05, pages 92-99, 2005. ACM Press.
• A. Storjohann and G. Villard. Computing the rank and a small nullspace basis of a polynomial matrix. In M. Kauers, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '05, pages 309-316. ACM Press.
• J. Gerhard, M.W. Giesbrecht, A. Storjohann and E.V. Zima. Shiftless decomposition and polynomial-time rational summation. In R. Sendra, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '03, pages 119-126, 2003. ACM Press.
• A. Storjohann. High-order lifting. In T. Mora, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '02, pages 246-254, 2002. ACM Press.
• A. Storjohann. Deterministic computation of the Frobenius form (Extended Abstract). In Proc. 42nd Annual Symp. Foundations of Comp. Sci., pages 368--377, 2001. IEEE Computer Society Press.
• M. Giesbrecht, M. Jacobson, and A. Storjohann. Algorithms for large integer matrix problems. In S. Boztas and I. E. Shparlinski, editors, Proc. AAECC-14, volume 2227 of Lect. Notes Comput. Sci., 2001. Springer Verlag.
• T. Mulders and A. Storjohann. Rational solutions of singular linear systems. In C. Traverso, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC 2000, pages 242-249, 2000. ACM Press.
• T. Mulders and A. Storjohann. Diophantine linear system solving. In S. Dooley, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '99, pages 281-288, 1999. ACM Press.
• T. Mulders and A. Storjohann. The modulo N extended gcd problem for polynomials. In O. Gloor, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '98, pages 105--112, 1998. ACM Press.
• A. Storjohann. An O(n^3) algorithm for Frobenius normal form. In O. Gloor, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '98, pages 101-104, 1998. ACM Press.
• A. Storjohann and T. Mulders. Fast algorithms for linear algebra modulo N. In G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, editors, Algorithms -- ESA '98, volume 1461 of Lect. Notes Comput. Sci., pages 139-150, 1998. Springer Verlag.
• A. Storjohann. A solution to the extended gcd problem with applications. In W. W. Küchlin, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '97, pages 109-116, 1997. ACM Press.
• A. Storjohann. Near optimal algorithms for computing Smith normal forms of integer matrices. In Y. N. Lakshman, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '96, pages 267-274, 1996. ACM Press.
• A. Storjohann and G. Labahn. Asymptotically fast computation of Hermite normal forms of integer matrices. In Y. N. Lakshman, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '96, pages 259-266, 1996. ACM Press.
• A. Storjohann and G. Labahn. Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation. In A. H. M. Levelt, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '95, pages 119-125, 1995. ACM Press.

Invited Papers:

• M. Giesbrecht, A. Storjohann, and G. Villard. Algorithms for matrix canonical forms. In Computer Algebra Handbook, J. Grabmeier, E. Kaltofen, and V. Weispfenning editors. Springer Verlag, 2002.

Technical Reports not Appearing Elsewhere:

• A. Storjohann. Notes on computing minimal approximant bases. In W. Decker, M. Dewar, E. Kaltofen, and S. Watt, editors, Challenges in Symbolic Computation Software, number 06271 in Dagstuhl Seminal Proceedings, Dagstuhl, Germany, 2006. Internationales Begegnungs- und Forshungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
• A. Storjohann. Faster algorithms for integer lattice basis reduction. Technical Report 249, Swiss Federal Institute of Technology, ETH- Zurich, Department of Computer Science, Zurich, Switzerland, July 1996.

Abstracts and/or Papers Read:

• A. Storjohann and G. Villard. Algorithms for similarity transforms (Extended Abstract). In T. Mulders, editor, Proc. Seventh Rhine Workshop on Computer Algebra: RWCA '00, pages 109--118, Bregenz, Austria, 2000.
• A. Storjohann. The triangularizing adjoint (Extended Abstract). In J. Calmet, editor, Proc. Sixth Rhine Workshop on Computer Algebra: RWCA '98, Sankt Augustin, Germany, 1998.

Other Awards and Honours:

• Best Poster Presentation, with Burcin Erocal, at the International Symposium on Symbolic and Algebraic Computation: ISSAC 2010, held in Munich, Germany.
  Title: "Nullspace Computation over Rational Function Fields for Symbolic Summation."
• Distinguised Poster Presentation, with Zhuliang Chen, at the International Symposium on Symbolic and Algebraic Computation: ISSAC 2004, held in Santander, Spain.
  Title: "An Implementation of Certified Linear System Solving for Integer Matrices."
• Best Poster Presentation, with Thom Mulders, at the International Symposium on Symbolic and Algebraic Computation: ISSAC 2000, held in St. Andrews, Scotland.
  Title: "Triangular Factorization of Polynomial Matrices."

Invited Addresses:

• 2009, NSF Workshop on Future Directions of Symbolic Computation Research and Their Applications to the Domain Sciences
  Title: "Certifying the rank of an integer matrix."
• 2008, Sage Days 10
  Title: ``Algorithms for Linear Algebra on Polynomial and Integer Matrices: Similarities and Differences.''
• 2008, Sage Develop Days 1
  Title: "Exact linear algebra."
• 2007, Canadian Mathematical Society Winter 2007 Meeting
  Title: "Faster algorithms for the Frobenius canonical form."
• 2006, Fields Institute Workshop on Computational Challenges Arising in Algorithmic Number Theory and Cryptography
  Title: "Speedy new algorithms for solving integer linear systems."
• 2006, Waterloo Workshop on Computer Algebra
  Title: "The vector rational reconstruction problem."
• 2006, Dagstuhl Seminar Number 06271 (Challenges in Symbolic Computation Software)
  Title: "Optimizing linear algebra computations."
• 2004, Dagstuhl Seminar Number 04061 (Real Computation and Complexity)
  Title: "Shifted number systems for safe semi-numeric computation."
• 2001, East Coast Computer Algebra Day
  Title: "Design and Analysis of Algorithms for Symbolic Linear Algebra."
• 2001, Scientific Committee's Invitational Special Session of the 7th International Conference on Applications of Computer Algebra
  Title: "Computing the Frobenius Canonical Form."

Teaching: (all at University of Waterloo)

• Spring 2010, "CS 887: Algorithms for Exact Linear Algebra"
• Winter 2010, "CS 487/687: Introduction to Computer Algebra"
• Fall 2009, "CS 135: Designing Functional Programs"
• Fall 2007, "CS 134: Principles of Computer Science"
• Spring 2007, "CS 240: Data Structures and Data Management"
• Winter 2007, "CS 487/687: Introduction to Computer Algebra"
• Fall 2006, "CS 341: Algorithms"
• Winter 2006, "CS 125: Introduction to Programming Principles"
• Spring 2005, "CS 341: Algorithms"
• Winter 2005, "CS 487/687: Introduction to Computer Algebra"
• Fall 2004, "CS 240: Data Structures and Data Management"
• Fall 2004, "CS 134: Principles of Computer Science"
• Fall 2003, "CS 240: Data Structures and Data Management"
• Fall 2003, "CS 134: Principles of Computer Science"
• Spring 2003, "CS 887: Algorithms for Symbolic and Exact Linear Algebra"
• Spring 2003, "CS 134: Principles of Computer Science"
• Fall 2002, "CS 134: Principles of Computer Science"
• Winter 2002, "CS 240: Data Structures and Data Management"
• Fall 2001, "CS 130: Developing Programming Principles"

Post doctoral student supervision

• Pascal Giorgi - 2006 (co-supervised)
• Clement Pernet - 2007 (co-supervised)

PhD students

• Dan Roche - current (co-supervised)
• Curtis Bright - current

Masters students

• Zhuliang Chen - completed in 2005
  Thesis Title: A BLAS based C library for exact linear algebra on integer matrices
• Zach Olesh - completed in 2006
  Thesis Title: The vector rational function reconstruction problem
• Li Qiao - (co-supervised) completed in 2007
  Thesis Title: Lattice compression of polynomial matrices
• Curtis Bright - completed in 2009
  Project Title: Vector Rational Number Reconstruction
• Johnny Valeriote - completed in 2010
  Project Title: Deterministic Solution of Rational Linear Systems of Polynomials over Abstract Fields
• Somit Gupta - current
• Soumojit Sarkar - current
• Azim Ansari - current