Efficient transitive closure of sparse matrices over closed semirings. (English) Zbl 1088.68042
Summary: This paper surveys several alternative data structures and algorithms for multiplying sparse upper-triangular matrices over closed semirings, and evaluates their efficiency in computing transitive closures of matrices over the Boolean semiring. Two new variants are introduced that outperform previously known methods on a collection of large data-sets drawn from linguistic applications.
MSC:
| 68P05 | Data structures |
| 68W30 | Symbolic computation and algebraic computation |
| 65F50 | Computational methods for sparse matrices |
| 68T50 | Natural language processing |
Keywords:
Sparse matrix multiplication; Semirings; Dijkstra’s algorithm; Typed feature logic; ParsingReferences:
| [1] | Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0326.68005 |
| [2] | Aı¨t-Kaći, H.; Boyer, R.; Lincoln, P.; Nasr, R., Efficient implementation of lattice operations, ACM Trans. Progr. Lang. Sys., 11, 1, 115-146 (1989) |
| [3] | Bentley, J., Programming Pearls (1986), Addison-Wesley: Addison-Wesley Reading, MA |
| [4] | Carpenter, B.; Penn, G., Compiling typed attribute-value logic grammars, (Bunt, H.; Tomita, M., Recent Advances in Parsing Technologies (1996), Kluwer: Kluwer Dordrecht), 145-168, see also http://www.ale.cs.toronto.edu |
| [5] | Cherkassky, B. V.; Goldberg, A. V.; Radzik, T., Shortest paths algorithms: theory and experimental evaluation, Math. Program., 73, 2, 129-174 (1996) · Zbl 0853.90111 |
| [6] | Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (1990) · Zbl 0702.65046 |
| [7] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002 |
| [8] | C. Fellbaum, (Ed.), WordNet: An Electronic Lexical Database, MIT Press, Cambridge, MA, 1998, see also http://www.cogsci.princeton.edu/\( \sim;\); C. Fellbaum, (Ed.), WordNet: An Electronic Lexical Database, MIT Press, Cambridge, MA, 1998, see also http://www.cogsci.princeton.edu/\( \sim;\) · Zbl 0913.68054 |
| [9] | Flickinger, D., On building a more efficient grammar by exploiting types, Natural Lang. Eng., 6, 1, 15-28 (2000), see also http://lingo.stanford.edu/erg.html |
| [10] | Floyd, R. W., Algorithm 97 (shortest path), Comm. ACM, 5, 6, 345 (1962) |
| [11] | Fredman, M. L., New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5, 1, 83-89 (1976) · Zbl 0326.68027 |
| [12] | Goldberg, A. V.; Radzik, T., A heuristic improvement of the bellman-ford algorithm, Appl. Math. Lett., 6, 3-6 (1993) · Zbl 0771.68091 |
| [13] | Goodman, J., Semiring parsing, Comput. Linguist., 25, 4, 573-605 (1999) |
| [14] | Johnson, D. B., Efficient algorithms for shortest paths in sparse networks, J. Assoc. Comput. Mach., 24, 1, 1-13 (1977) · Zbl 0343.68028 |
| [15] | D.S. Johnson, C.C. McGeoch, (Eds.), Network flows and matching: first DIMACS implementation challenge, Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, American Mathematical Society, Providence, RI, 1991.; D.S. Johnson, C.C. McGeoch, (Eds.), Network flows and matching: first DIMACS implementation challenge, Series in Discrete Mathematics and Theoretical Computer Science, Vol. 12, American Mathematical Society, Providence, RI, 1991. · Zbl 0781.00013 |
| [16] | Laderman, J.; Pan, V.; Sha, X.-H., On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl., 162-164, 557-588 (1992) · Zbl 0748.65043 |
| [17] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059 |
| [18] | Lee, L., Fast context-free grammar parsing requires fast Boolean matrix multiplication, J. ACM, 49, 1, 1-15 (2002) · Zbl 1323.68332 |
| [19] | Penn, G., The algebraic structure of transitive closure and its application to attributed type signatures, Grammars, 3, 2-3, 295-312 (2000) · Zbl 0973.68044 |
| [20] | Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; Vetterling, W. T., Numerical Recipes in C: The Art of Scientific Computing (1993), Cambridge University Press: Cambridge University Press Cambridge |
| [21] | Rector, A. L.; Rogers, J. E.; Pole, P., The GALEN high-level ontology, (Proc. 14th Internat. Congr. of the European Federation for Medical Informatics (MIE-96), Part A. Proc. 14th Internat. Congr. of the European Federation for Medical Informatics (MIE-96), Part A, IOS Press (1996)), 174-178, see also http://www.opengalen.org |
| [22] | Strassen, V., Gaussian elimination is not optimal, Numer. Math., 14, 3, 354-356 (1969) · Zbl 0185.40101 |
| [23] | Warshall, S., A theorem on Boolean matrices, J. ACM, 9, 1, 11-12 (1962) · Zbl 0118.33104 |
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.
