Selected Publications of Arne Storjohann

Preprints

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. Accepted for publication in the Journal of Algorithms. Updated draft ps (May 3, 2005), 25pp.


Refereed papers

20l7

C.~Pernet and A.~Storjohann, Time and space efficient generators for quasiseparable matrices. Time and space efficient generators for quasiseparable matrices. Journal of Symbolic Computation, Special Issue for ISSAC'16. In press, 2017. pdf.

S. Aflaki, M. Volk, B. Bonakdarpour, J.-P. Katoen and A. Storjohann, Automated fine-tuning of probabilistic self-stabilizing algorithms. Proceedings of the IEEE Symposium on Reliable Distributed Systems (SRDS), 2017. To appear. pdf.

E. L. Kaltofen, C. Pernet, A. Storjohann, C. Waddell, Early termination in parametric linear system solving and rational function vector recovery with error correction. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'17), ACM Press, 2017, 237--244. pdf.

M. Khochtali, J. Rosenkilde, A. Storjohann, Popov form computation for matrices of Ore polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'17), ACM Press, 2017, 253--260. pdf.

20l6

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

20l5

E. Kaltofen and A. Storjohann, The complexity of computational problems in exact linear algebra. Chapter in Björn Enquist, editor, Encyclopedia of Applied and Computational Mathematics, Volumn 1, 2015, Springer,227--233. pdf

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 September 18, 2017.