The shifted number system for fast linear algebra on integer matrices

作     者：Storjohann, A 

作者机构：Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada 

出 版 物：《JOURNAL OF COMPLEXITY》 (复杂性杂志)

年 卷 期：2005年第21卷第4期

页      面：609-650页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Natural Sciences and Engineering Research Council of Canada  NSERC  (RGPIN 26082-03) 

主　　题：integer matrix matrix determinant linear system solving Las Vegas algorithms bit complexity matrix multiplication 

摘      要：The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality certification techniques of Storjohann 2003 for polynomial matrices are extended to the integer case. Las Vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient. (c) 2005 Elsevier Inc. All rights reserved.