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

Berkowitz, Stuart J.

Inf. Process. Lett. 18, 147-150 (1984).

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).

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

parallel algebraic circuit complexity; upper bounds; matrix; determinant; characteristic polynomial; adjoint; commutative ring; Turing machine

References:

[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)