Article

Free access

Arithmetic complexity of unordered sparse polynomials

Authors:

F. Gustavson,

D. Y. Y. YunAuthors Info & Claims

SYMSAC '76: Proceedings of the third ACM symposium on Symbolic and algebraic computation

Pages 149 - 153

https://doi.org/10.1145/800205.806333

Published: 10 August 1976 Publication History

PDF eReader

Abstract

In this paper, we show that addition and subtraction of unordered sparse polynomials can be done in time m+n and multiplication in time m+n. So we see already that if a particular sequence of polynomials computation involves a combination of these arithmetic operations as well as tests for equivalence or zero while intermediate expressions are not important enough to be displayed, then the unordered representation could amount to substantial savings in computation time. The visual demand of human users can still be satisfied at the cost of a single sort of the final answer as opposed to sorting each intermediate result in the case of ordered representations.

References

[1]

Knuth, D. E., "The Art of Computer Programming. Seminumerical Algorithm," Vol. 2, Addison Wesley Publ. Co., Reading, Mass. 1969.

Digital Library

Google Scholar

[2]

Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithm," Addison Wesley Publ. Co., Reading, Mass. 1974.

Digital Library

Google Scholar

[3]

Johnson, S. C., "Sparse Polynomial Arithmetic," Proceedings of Eurosam '74, pp. 63-71, (ACM SIGSAM Bull., Vol. 8, No. 3, August 1974, Issue No. 31).

Digital Library

Google Scholar

[4]

Gustavson, F. G., "An Efficient Algorithm to Perform Sparse Matrix Multiplication," to appear.

Google Scholar

Cited By

View all

Norman AMoore P(2005)The initial design of a vector based algebra systemSymbolic and Algebraic Computation10.1007/3-540-09519-5_78(258-265)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09519-5_78
Matooane ’Norman A(1999)A Parallel Symbolic Computation Environment: Structures and MechanicsEuro-Par’99 Parallel Processing10.1007/3-540-48311-X_212(1492-1495)Online publication date: 6-Aug-1999
https://doi.org/10.1007/3-540-48311-X_212
Carter JWegman M(1979)Universal classes of hash functionsJournal of Computer and System Sciences10.1016/0022-0000(79)90044-818:2(143-154)Online publication date: Apr-1979
https://doi.org/10.1016/0022-0000(79)90044-8
Show More Cited By

Index Terms

Arithmetic complexity of unordered sparse polynomials

Recommendations

Monotone Arithmetic Complexity of Graph Homomorphism Polynomials
Abstract
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for ...
Convolution formulas for multivariate arithmetic Tutte polynomials
Abstract
The multivariate arithmetic Tutte polynomial of arithmetic matroids is a generalization of the multivariate Tutte polynomial of matroids. In this note, we give the convolution formulas for the multivariate arithmetic Tutte polynomial of the ...
Complexity analysis of hypergeometric orthogonal polynomials

The complexity measures of the Crámer-Rao, Fisher-Shannon and LMC (López-Ruiz, Mancini and Calvet) types of the Rakhmanov probability density n ( x ) = ω ( x ) p n 2 ( x ) of the polynomials p n ( x ) orthogonal with respect to the weight function ω ( x ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SYMSAC '76: Proceedings of the third ACM symposium on Symbolic and algebraic computation

August 1976

393 pages

ISBN:9781450377904

DOI:10.1145/800205

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)5

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Norman AMoore P(2005)The initial design of a vector based algebra systemSymbolic and Algebraic Computation10.1007/3-540-09519-5_78(258-265)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09519-5_78
Matooane ’Norman A(1999)A Parallel Symbolic Computation Environment: Structures and MechanicsEuro-Par’99 Parallel Processing10.1007/3-540-48311-X_212(1492-1495)Online publication date: 6-Aug-1999
https://doi.org/10.1007/3-540-48311-X_212
Carter JWegman M(1979)Universal classes of hash functionsJournal of Computer and System Sciences10.1016/0022-0000(79)90044-818:2(143-154)Online publication date: Apr-1979
https://doi.org/10.1016/0022-0000(79)90044-8
Carter JWegman MHopcroft JFriedman EHarrison M(1977)Universal classes of hash functions (Extended Abstract)Proceedings of the ninth annual ACM symposium on Theory of computing10.1145/800105.803400(106-112)Online publication date: 4-May-1977
https://dl.acm.org/doi/10.1145/800105.803400

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Monotone Arithmetic Complexity of Graph Homomorphism Polynomials

Convolution formulas for multivariate arithmetic Tutte polynomials

Complexity analysis of hypergeometric orthogonal polynomials