On computing the determinant in small parallel time using a small number of processors. (English) Zbl 0541.68019

Summary: The determinant, characteristic polynomial and adjoint over an arbitrary commutative ring with unity can be computed by a circuit with size \(O(n^{3.496})\) and depth O\((log{}^ 2n)\). Furthermore, the circuits can be constructed uniformly (by a log space bounded Turing machine).


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0326.68005
[2] Beame, P., Private communication (1982)
[3] Borodin, A.; Gathen, J.von zur; Hopcroft, J., Fast parallel matrix and GCD computations (1981), Preprint
[4] Coopersmith, D.; Winograd, S., On the asymptotic complexity of matrix multiplication, Proc. 22nd Symp. on Foundations of Computer Science, 82-90 (1981)
[5] Csanky, L., Fast parallel inversion algorithms, SIAM J. Comput., 5, 4, 818-823 (1976) · Zbl 0353.68063
[6] Faddeev, D.; Faddeev, V., Computational Methods of Linear Algebra, 247-251 (1963), Freeman, San Francisco
[7] Ladner, R.; Fischer, M., Parallel prefix computations, J. ACM, 27, 831-838 (1980) · Zbl 0445.68066
[8] Samuelson, P. A., A method for determining explicity the coefficients of the characteristic equation, Ann. Math. Statist., 13, 424-429 (1942) · Zbl 0061.27304
[9] Valiant, L.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput. (1982), submitted for publication · Zbl 0524.68028
[10] Winograd, S., Private communication (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.