Return to Answer

fixed typo

edited Nov 28, 2017 at 18:39

1
11
156
377

I don't know what algorithm Sage actually uses, but computing rank over the integers is fun and easy: Complexity of computing matrix rank over integers . It is NOT so easy if you want good running time, and for that there are a number of papers of Arne Storjohann, which show that one can do it asymptotically as fast as for real matrices (a surprising result, in view of coefficient blow-up). Storjohann has actually implemented his algorithms, and I am sure Sage uses this or something like it.

Chen, Zhuliang; Storjohann, Arne, A BLAS based C library for exact linear algebra on integer matrices, Kauers, Manuel (ed.), Proceedings of the 2005 international symposium on symbolic and algebraic computation, ISSAC’05, Beijing, China, July 24--27, 2005. New York, NY: ACM Press (ISBN 1-59593-095-7). 92-99 (2005). ZBL1360.65086.

As for the reals, the fastest way to compute rank is to compute the singular value decomposition, and throw away singular values below some cutoff (probably around $10^-6$$10^{-6}$). As pointed out by many in the comments, rank is very unstable, so unless you want the "pseudo-rank" (as above, defined by the size of the singular values), don't go there.

I don't know what algorithm Sage actually uses, but computing rank over the integers is fun and easy: Complexity of computing matrix rank over integers . It is NOT so easy if you want good running time, and for that there are a number of papers of Arne Storjohann, which show that one can do it asymptotically as fast as for real matrices (a surprising result, in view of coefficient blow-up). Storjohann has actually implemented his algorithms, and I am sure Sage uses this or something like it.

Chen, Zhuliang; Storjohann, Arne, A BLAS based C library for exact linear algebra on integer matrices, Kauers, Manuel (ed.), Proceedings of the 2005 international symposium on symbolic and algebraic computation, ISSAC’05, Beijing, China, July 24--27, 2005. New York, NY: ACM Press (ISBN 1-59593-095-7). 92-99 (2005). ZBL1360.65086.

As for the reals, the fastest way to compute rank is to compute the singular value decomposition, and throw away singular values below some cutoff (probably around $10^-6$). As pointed out by many in the comments, rank is very unstable, so unless you want the "pseudo-rank" (as above, defined by the size of the singular values), don't go there.

I don't know what algorithm Sage actually uses, but computing rank over the integers is fun and easy: Complexity of computing matrix rank over integers . It is NOT so easy if you want good running time, and for that there are a number of papers of Arne Storjohann, which show that one can do it asymptotically as fast as for real matrices (a surprising result, in view of coefficient blow-up). Storjohann has actually implemented his algorithms, and I am sure Sage uses this or something like it.

Chen, Zhuliang; Storjohann, Arne, A BLAS based C library for exact linear algebra on integer matrices, Kauers, Manuel (ed.), Proceedings of the 2005 international symposium on symbolic and algebraic computation, ISSAC’05, Beijing, China, July 24--27, 2005. New York, NY: ACM Press (ISBN 1-59593-095-7). 92-99 (2005). ZBL1360.65086.

As for the reals, the fastest way to compute rank is to compute the singular value decomposition, and throw away singular values below some cutoff (probably around $10^{-6}$). As pointed out by many in the comments, rank is very unstable, so unless you want the "pseudo-rank" (as above, defined by the size of the singular values), don't go there.

answered Nov 28, 2017 at 18:20

1
11
156
377

I don't know what algorithm Sage actually uses, but computing rank over the integers is fun and easy: Complexity of computing matrix rank over integers . It is NOT so easy if you want good running time, and for that there are a number of papers of Arne Storjohann, which show that one can do it asymptotically as fast as for real matrices (a surprising result, in view of coefficient blow-up). Storjohann has actually implemented his algorithms, and I am sure Sage uses this or something like it.

Chen, Zhuliang; Storjohann, Arne, A BLAS based C library for exact linear algebra on integer matrices, Kauers, Manuel (ed.), Proceedings of the 2005 international symposium on symbolic and algebraic computation, ISSAC’05, Beijing, China, July 24--27, 2005. New York, NY: ACM Press (ISBN 1-59593-095-7). 92-99 (2005). ZBL1360.65086.

As for the reals, the fastest way to compute rank is to compute the singular value decomposition, and throw away singular values below some cutoff (probably around $10^-6$). As pointed out by many in the comments, rank is very unstable, so unless you want the "pseudo-rank" (as above, defined by the size of the singular values), don't go there.