Fast and Efficient Parallel Algorithms for the Exact Inversion of Integer Matrices
Fast and Efficient Parallel Algorithms for the Exact Inversion of Integer Matrices
复制标题
整数矩阵精确逆的快速高效并行算法
DOI：
10.1007/3-540-16042-6_29
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
V. Pan
中科院分区：
文献类型：
--
作者：
V. Pan
Let A = (aij) be a nonsingular n×n integer matrix such that log ∥A∥ ≤ no(1),|aij| ≤ ∥A∥ ≤ n|aij|. Then adj A, A−1and all the coefficients of the characteristic polynomial of A including det A can be exactly evaluated on arithmetic circuits using O(log2n) parallel steps and M(n) processors where M(n) is the minimum number of processors required in order to multiply two n×n matrices in O(log n) steps, M(n) = o(n2.5). This substantially improves the processor boundM(n) of [Preparata and Sarwate, 78] and extends the recent results of [Pan and Reif, 85], where the same complexity estimates were obtained for the approximate evaluation of A−1and under the additional assumption that A is a well-conditioned or strongly diagonally dominant matrix. All arithmetic operations can be performed with the precision of ≤ d bits so the total cost of computation is only O(log(dn))2steps, o(n2.496d log d log log d) processors under the Boolean circuit model of parallel computation. Here d is O(n2log(n∥A∥) in the worst case; d is O(n log(n∥A∥)) with probability 1-O(1/(nh−1∥A∥h)) for arbitrary constant h. This extends our-improvement of the efficiency of the previously known algorithms to the case of the Boolean circuit model and consequently increases the efficiency of the known parallel algorithms for several related algebraic and combinatorial problems.
