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 2007 -- present

Education, Employment:

2002--2007

Assistant Professor at the David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada

2001--2002

Postdoc at the Ontario Research Center for Computer Algebra

2000

PhD 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

MMath 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

BMath 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:

• W. Zhou, G. Labahn and A. Storjohann. A deterministic algorithm for inverting a polynomial matrix. To appear in Journal of Complexity.
• 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.
• C.-P. Jeannerod, C. Pernet and A. Storjohann. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. Journal of Symbolic Computation, 56:46-58, 2013.
• Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x]. Journal of Symbolic Computation: Special issue in honour of the research and influence of Joachim von zur Gathen at 60, 47(4):422-453, 2012.
• 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 and S. Yang. Linear independence oracles and applications to rectangular and low rank linear systems. In K. Nabeshima, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '14, pages 381-388, 2014. ACM Press.
• C. Pauderis and A. Storjohann. Computing the invariant structure of integer matrices: fast algorithms into practice. In M. Kauers, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '13, pages 307-314, 2013. ACM Press.
• C. Pauderis and A. Storjohann. Deterministic unimodularity certification. In J. van der Hoeven and M. van Hoeij, editors, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '12, pages 281-288, 2012. ACM Press.
• W. Zhou and G. Labahn and A. Storjohann. Computing minimal nullspace bases. In J. van der Hoeven and M. van Hoeij, editors, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '12, pages 366-373, 2012. ACM Press.
• S. Gupta and A. Storjohann. Computing Hermite forms of polynomial matrices. In A. Leykin, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '11 , pages 297-303, 2011. ACM Press. In A. Leykin, editor,
• S. Sarkar and A. Storjohann. Normalization of row reduced matrices. In A. Leykin, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '11 , pages 155-162, 2011. ACM Press.
• C. Bright and A. Storjohann. Vector rational number reconstruction. In A. Leykin, editor, Proc. Int'l. Symp. on Symbolic and Algebraic Computation: ISSAC '11, pages 51-57, 2011. ACM Press.
• 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:

• 2013, International Linear Algebra Society
  Title: "Computing the invariant structure of integer matrices"
• 2013, SIAM Conference on Applied Algebraic Geometry
  Title: "Lattice reduction of polynomial matrices"
• 2012, Workshop on Efficient Linear Algebra for Gröbner Basis Computations
  Title: "Double-plus-one lifting and applications to lattice problems."
• 2011, Sage/Flint Days Workshop at Warwick University
  Title: "Some ideas for efficient implementation of algorithms for polynomial matrix computations."
• 2011, École Normale Supérieure de Lyon
  Title: "Inverting Integer and Polynomial Matrices."
• 2010, Jo60: A Modern Computer Algebraist
  Title: "Inverting Integer and Polynomial Matrices."
• 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)

• Fall 2014, "CS 240: Data Structures and Data Management"
• Fall 2014, "CS 240: Data Structures and Data Management"
• Fall 2013, "CS 240: Data Structures and Data Management"
• Fall 2013, "CS 240: Data Structures and Data Management"
• Winter 2013, "CS 487/687: Introduction to Computer Algebra"
• Fall 2012, "CS 240: Data Structures and Data Management"
• Fall 2012, "CS 240: Data Structures and Data Management"
• Winter 2012, "CS 487/687: Introduction to Computer Algebra"
• Winter 2012, "CS 240: Data Structures and Data Management"
• Spring 2011, "CS 240: Data Structures and Data Management"
• Spring 2011, "CS 240: Data Structures and Data Management"
• Fall 2010, "CS 240: Data Structures and Data Management"
• 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)
• Andy Novocin -- 2012 (co-supervised)
• Romain Lebreton -- 2013 (co-supervised)

PhD students

• Dan Roche - completed in 2011 (co-supervised)
  Project Title: Efficient Computation with Sparse and Dense Polynomials
• 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
  Thesis Title: Vector rational number reconstruction
• Johnny Valeriote - completed in 2010
  Thesis Title: Deterministic solution of rational linear systems of polynomials over abstract fields
• Somit Gupta - completed in 2011
  Thesis Title: Computing Hermite forms of polynomial matrices
• Soumojit Sarkar - completed in 2011
  Thesis Title: Computing Popov forms of polynomial matrices
• Colton Pauderis - completed 2013
  Thesis Title: Deterministic umimodularity certification and applications for integer matrices
• Shiyun Yang - completed 2014
  Thesis Title: Algorithms for fast linear system solving and rank profile computation
• Alex Krueger - completed 2014
  Thesis Title: Randomized algorithms for computing the rank profile of a matrix over a finite field
• Vijay Menon - in progress
• Lawrence Barret - (co-supervised) in progress