Selected Publications of Arne Storjohann

Preprints

E. Kaltofen and A. Storjohann, The complexity of computational problems in exact linear algebra. In Encyclopedia of Applied and Computational Mathematics, Björn Enquist, editor, Springer, 2012, to appear. Mathematics of Computer Science, Discrete Mathematics, Håstad, Johan (field editor). pdf

C. Pernet and A. Storjohann, Frobenius form in expected matrix multiplication time over sufficiently large fields. Preprint pdf (November 30, 2007), 27pp.

A. Storjohann, Notes on computing minimal approximant bases. Dagstuhl preprint link to pdf (August 21, 2006), 6pp.

Z. Chen and A. Storjohann, Lattice compression of integer matrices. Accepted for publication in the Journal of Symbolic Computation. Draft ps (December 14, 2005), 14pp. Maple computations: input and output.

A. Storjohann, The modulo extended gcd problem and space efficient algorithms for integer matrices. To appear in Journal of Algorithms. Updated draft ps (May 3, 2005), 25pp.


Refereed papers

20l6

J. S. Rosenkilde and A. Storjohann, Algorithms for simultaneous Pade approximationse. Algorithms for simultaneous Pade approximations. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'16), ACM Press, 2016, 405--412. pdf.

20l5

A. Storjohann and S. Yang, A relaxed algorithm for online matrix inverse. A relaxed algorithm for online matrix inversion. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'15), ACM Press, 2015, 8pp. pdf.

A. Storjohann, On the complexity of inverting integer and polynomial matrices. Computational Complexity, 2015, v. 24, pp. 777-821 pdf

20l4

W. Zhou, G. Labahn and A. Storjohann, A deterministic algorithm for inverting a polynomial matrix. Journal of Complexity, 2015, v. 31, pp. 162-173. pdf

A. Storjohann and S. Yang, Linear independence oracles and applications to rectangular and low rank linear systems. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'14), ACM Press, 2014, 8pp. pdf.

2013

C.-P. Jeannerod, C. Pernet and A. Storjohann, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. Journal of Symbolic Computation, 2013. pdf.

C. Pauderis and A. Storjohann, Computing the invariant structure of integer matrices: fast algorithms into practice. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'13), ACM Press, 2013, 8pp. pdf.

2012

S. Gupta, S. Sarkar, A. Storjohann, J. Valeriote, 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, 2012, v. 47(4), pp. 422-453. pdf.

C. Pauderis and A. Storjohann, Deterministic unimodularity certification. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'12), ACM Press, 2012, 8pp. pdf.

W. Zhou, G. Labahn and A. Storjohann, Computing minimal nullspace bases. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'12), ACM Press, 2012, 8pp. pdf.

2011

S. Gupta and A. Storjohann, Computing Hermite forms of polynomial matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'11), ACM Press, 2011, 8pp. pdf.

S. Sarkar and A. Storjohann, Normalization of row reduced matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'11), ACM Press, 2011, 7pp. pdf.

C. Bright and A. Storjohann, Vector rational number reconstruction. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'11), ACM Press, 2011, 7pp. pdf.

2009

A. Storjohann, Integer matrix rank certification. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'09), ACM Press, 2009, 8pp. pdf. pdf

2007

Z. Olesh and A. Storjohann, The vector rational function reconstruction problems. Proceedings of the Waterloo Workshop on Computer Algebra: devoted to the 60th birthday of Sergei Abramov (WWCA), World Scientific, 2007, pp. 137-149. pdf

C. Pernet and A. Storjohann, Faster algorithms for the characteristic polynomial. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'07), ACM Press, 2007, 8pp. pdf.

W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard, Faster inversion and other black box matrix computations using efficient block projections. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'07), ACM Press, 2007, 8pp. pdf.

2006

W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard, Solving sparse rational linear systems. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'06), ACM Press, 2006, pp. 63-70. pdf.

2005

A. Storjohann, The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, 2005, v. 21(4), pp. 609-650. pdf.

Z. Chen and A. Storjohann, A BLAS based C library for exact linear algebra on integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'05), ACM Press, 2005, pp. 92-99. pdf.

A. Storjohann and G. Villard, Computing the rank and a small nullspace basis of a polynomial matrix. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'05), ACM Press, 2005, pp. 309-316. pdf. Extended version: pdf.

2004

T. Mulders and A. Storjohann, Certified dense linear system solving. Journal of Symbolic Computation, 2004, v. 37(4), pp. 485-510. pdf.

D. Saunders, A. Storjohann and G. Villard, Matrix rank certification. Electronic Journal of Linear Algebra, 2004, v. 11, pp. 16-23.

2003

A. Storjohann, High-order lifting and integrality certification. Journal of Symbolic Computation, 2003, v. 36(3-4), pp. 613-648. pdf.

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices. Journal of Symbolic Computation, 2003, v. 35(4), pp. 377-401. pdf.

J. Gerhard, M.W. Giesbrecht, A. Storjohann and E.V. Zima. Shiftless decomposition and polynomial-time rational summation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'03), ACM Press, 2003, pp. 119-126. pdf.

M. Giesbrecht, A. Storjohann and G. Villard. Algorithms for matrix canonical forms. Invited Submission. Computer Algebra Handbook: Foundations, Applications, Systems. Springer Verlag, pp. 38-41, 2003.

2002

M. Giesbrecht and A. Storjohann, Computing rational forms of integer matrices. Journal of Symbolic Computation, 2002, v. 34(3), pp. 157-172.

A. Storjohann, High-order lifting Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'02), ACM Press, 2002, pp. 246-254. pdf.

2001

M. Giesbrecht, M. Jacobson, Jr. and A. Storjohann, Algorithms for large integer matrix problems. S. Boztas and I. E. Shparlinski, editors, Proc. AAECC-14,, volume 2227 of Lect. Notes Comput. Sci., Heidelberg, Germany, 2001. Springer Verlag.

A. Storjohann, Deterministic computation of the Frobenius form (Extended Abstract). In Proc. 42nd Annual Symp. Foundations of Comp. Sci., pages 368--377, Los Alamitos, California, 2001. IEEE Computer Society Press.

2000

T. Mulders and A. Storjohann, Rational solutions of singular linear systems. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'00), ACM Press, 2000, pp. 242-249.

A. Storjohann and G. Villard, Algorithms for Similarity Transforms. Rhine Workshop on Computer Algebra, Bregenz, Austria, 2000. Updated draft ps (May, 2005), 11pp.

1999

T. Mulders and A. Storjohann, Diophantine linear system solving. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'99), ACM Press, 1999, pp. 181-188. pdf.

1998

A. Storjohann, Computing Hermite and Smith normal forms of triangular integer matrices. Linear Algebra and its Applications, 1998, v. 282, pp. 25-45.

A. Storjohann, An O(n^3) algorithm for Frobenius normal form. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'98), ACM Press, 1998, pp. 101-104. pdf.

T. Mulders and A. Storjohann, The modulo N extended gcd problem for polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'98), ACM Press, 1998, pp. 105-112. pdf.

A. Storjohann and T. Mulders, Fast algorithms for linear algebra modulo N. Algorithms - ESA'98, Lecture Notes in Computer Science 1461, 1998, pp. 139-150. pdf.

1997

A. Storjohann and G. Labahn, A fast Las Vegas algorithm for computing Smith normal form of a polynomial matrix. Linear Algebra and its Applications, 1997, v. 253, pp. 155-173. pdf.

A. Storjohann, A solution to the extended gcd problem with applications. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'97), ACM Press, 1997, pp. 109-116. pdf.

1996

A. Storjohann, Nearly optimal algorithms for computing Smith normal forms of integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 267-274. pdf.

A. Storjohann and G. Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'96), ACM Press, 1996, pp. 259-266. pdf.

1995

A. Storjohann and G. Labahn, Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'95), ACM Press, 1995, pp. 119-125. pdf.


Dissertations

Computation of Hermite and Smith Normal Forms of Matrices. Master's Thesis. Department of Computer Science, University of Waterloo, 1994. Distributed as Postscript (662k), DVI (381k).

Algorithms for Matrix Canonical Forms. PhD Thesis. Department of Computer Science, Swiss Federal Institute of Technology -- ETH, 2000. Distributed as a 2up display version as PDF (980k), pp. 100.


Last modified April 27, 2015