Loading...
Please wait, while we are loading the content...
Similar Documents
A Combinatorial Algorithm for the Determinant (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Mahajan, Meena Vinay, V. |
| Description | We show the first efficient combinatorial algorithm for the computation of the determinant. Hitherto, all (known) algorithms for determinant have been based on linear algebra. In contrast, our algorithm and its proof of correctness are totally combinatorial in nature. The algorithm requires no division and works on arbitrary commutative rings. It also lends itself to efficient sequential and parallel implementations. 1 Introduction The Determinant has been the subject of study for over 200 years. Its history can be traced back to Leibnitz, Crammer, Vandermode, Binet, Cauchy, Jacobi, Gauss and others. Given its importance in linear algebra in particular and in geometry in general, it is not surprising that a galaxy of great mathematicians investigated the determinant from varied viewpoints. The algorithmic history of the determinant is as old as the mathematical concept itself. After all, the determinant was invented to solve systems of linear equations. Much of the initial effort was... In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms |
| File Format | |
| Language | English |
| Publisher | ACM/SIAM |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Initial Effort Arbitrary Commutative Ring Linear Equation Algorithmic History Varied Viewpoint Combinatorial Algorithm Parallel Implementation First Efficient Combinatorial Algorithm Mathematical Concept Great Mathematician Linear Algebra |
| Content Type | Text |
| Resource Type | Article |
