Several designs are presented for VLSI dictionary machines that combine both a linear (modify) network and a logarithmic (query) network with a novel idea for separation of concerns. The initial design objectives included: (1) single-cycle operability of host-issued modify and query commands (no compress instructions), (2) complete processor utilization (no waste processors), and (3) optimal 2 log n response times, where n is the current population of the machine. The authors sought simple ideas that, for the first time, would allow all three objectives to be achieved simultaneously. They were forced to abandon objective (3), instead achieving a slightly weaker objective, namely, near-optimal (2 log n+R) response times, where R is the time for a round trip through the particular prenetwork used to connect the host to the roots of the query trees in the logarithmic network. Both sorted and unsorted versions of dictionary machines are presented. Those with orthogonal command networks achieve all objectives; those without orthogonal networks achieve only the first and third.>

A combined methodology is presented for specifying abstract synchronous data types and proving the correctness of systolic network implementations. It is shown that an extension of the Parnas trace method of specifying software modules containing distinct access programs yields a natural method of specifying abstract synchronous data types that possess distinct access operators and are intended for implementation in VLSI. Associated systematic proof techniques are presented, and the correctness of several novel systolic network implementations of familiar data types is established. The methodology appears to be naturally suited to systolic network implementations with their associated rippling of control flow and data flow. The important distinction between systolic control-flow networks and systolic data-flow networks is presented.>

This paper presents an improved adaptive hybrid algorithm for multiplying dense multivariate polynomials that is both time and space efficient. The hybrid algorithm makes use of two families of univariate algorithms, one Karatsuba based and the other DFT based, which are applied recursively to solve the multivariate problem. The hybrid algorithm is adaptive in that particular univariate algorithms are selected at run time to minimize the time complexity; an order-of-magnitude speedup with respect to classical multiplication is achieved over the entire practical range except for very small problems. Empirical investigation shows that most of the theoretical superiority is maintained in actual implementation. The largest contribution to the space requirements of the total algorithm is determined by the univariate algorithm used for the outermost variable; except for quite small problems, selecting univariate algorithms to minimize run time almost always leads to situations where the space requirements of the total algorithm are extremely close to the space required merely to store the result.

Previous article Full AccessCorrigendum: A Family of Algorithms for Powering Sparse PolynomialsDavid K. Probst and Vangalur S. AlagarDavid K. Probst and Vangalur S. Alagarhttps://doi.org/10.1137/0209033PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Corrigendum: A Family of Algorithms for Powering Sparse Polynomials." SIAM Journal on Computing, 9(2), p. 439 Previous article FiguresRelatedReferencesCited byDetails Volume 9, Issue 2| 1980SIAM Journal on Computing History Published online:13 July 2006 InformationCopyright © 1980 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0209033Article page range:pp. 439-439ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

We discuss four new algorithms from a family of algorithms for computing integer powers of sparse polynomials. The four algorithms form a sequence of successively better algorithms; even the first member of the sequence shows an improvement in the leading term of the cost function in comparison with the best previously known binomial-expansion algorithm. To quote one result, if f is a 32-term sparse polynomial, computing $f * f^9 $ takes $8.75 \times 10^9 $ multiplications, while the best new algorithm computes $f^{10} $ from scratch using $1.125 \times 10^9 $ multiplications. The time and space analyses given support the conjecture that the best new algorithm is optimal for time and space within the family of sequential binomial-expansion algorithms for this problem. If the input polynomial has t terms, then the nth power may be computed by this algorithm with a time complexity of \[ \frac{{t^n }}{{n!}} + t^{n - 1} \left[ \frac{1}{{2(n - 2)!}} + \frac{1}{{2^{n - 2} (n - 1)!}}\right] + O(t^{n - 2} ),\quad n > 2 , \] and a space complexity of \[ \frac{{t^{n - 1} }}{{2^{2n - 4} (n - 1)!}} + O(t^{n - 2} ),\quad n > 2. \]