×

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
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA
[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 Reading, MA
[4] Carpenter, B.; Penn, G., Compiling typed attribute-value logic grammars, (), 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\)wn. · 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. · 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 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
[21] Rector, A.L.; Rogers, J.E.; Pole, P., The GALEN high-level ontology, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.