Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-06T08:09:58.218Z Has data issue: false hasContentIssue false

6 - Polynomial expressions

Published online by Cambridge University Press:  03 May 2010

Ryan Kastner ,
Anup Hosangadi  and
Farzan Fallah
Ryan Kastner
Affiliation:
University of California, San Diego
Anup Hosangadi
Affiliation:
University of California, Santa Barbara
Farzan Fallah
Affiliation:
Stanford University, California
Get access

Summary

Chapter overview

This chapter presents some of the issues in the optimization of polynomial expressions. The chapter starts with an introduction to polynomial expressions and their possible optimizations, with illustrative examples. Then, the details of some techniques for manipulating polynomial expressions are presented. This is followed by a description of algebraic techniques used for the optimization of multiple-variable polynomial expressions. The usefulness of these techniques is demonstrated through experimental results. Finally, the chapter presents an ILP-based approach to obtain the optimal solution to the problem.

Polynomial expressions

A polynomial is an expression constructed from one or more variables and constants using the operations addition, subtraction, multiplication, and raising to the power of nonnegative integer numbers. Examples of polynomial functions are: x3 – 6x2 + 10 and x3y2 + 15x2y2 – 6zx4. The first is a univariate polynomial, while the second is a multivariate polynomial. Univariate polynomials consist of at most one distinct variable, whereas multivariate polynomials can contain any number of variables.

A polynomial function can be thought as a summation of terms (both positive and negative). The degree of a term is the sum of the powers of each variable of the term. The degree of the term with the highest degree is the polynomial's degree. For example, the degree of the first aforementioned polynomial is 3, while the degree of the second polynomial is 5.

Polynomial functions are used to encode a number of problems in basic sciences such as chemistry and physics.

Type
Chapter
Information
Arithmetic Optimization Techniques for Hardware and Software Design , pp. 95 - 125
Publisher: Cambridge University Press
Print publication year: 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bartels, R. H., Beatty, J. C., and Barsky, B. A., An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. San Francisco, CA: Morgan Kaufmann Publishers, Inc., 1987.Google Scholar
Hearn, D. and Baker, M. P., Computer Graphics, 2nd edition. Upper Saddle River, NJ: Prentice-Hall Inc.
,GNU C Library, http://www.gnu.org/software/libc
Aho, A. V. and Johnson, S. C., Optimal code generation for expression trees, Journal of the ACM, 23 488–501, 1976.CrossRefGoogle Scholar
Sethi, R. and Ullman, J. D., The generation of optimal code for arithmetic expressions, Journal of the ACM, 17, 715–28, 1970.CrossRefGoogle Scholar
Aho, A. V., Johnson, S. C., and Ullman, J. D., Code generation for expressions with common subexpressions, Journal of the ACM, 24, 146–60, 1977.CrossRefGoogle Scholar
Breuer, M. A., Generation of optimal code for expressions via factorization, Communication of the ACM, 12, 333–40, 1969.CrossRefGoogle Scholar
Becker, T. and Weispfenning, V.. Grobner Bases. New York. NY: Springer-Verlag, 1993.CrossRefGoogle Scholar
Micheli, G. D., Synthesis and Optimization of Digital Circults: New York, NY: McGraw-Hill, Inc, 1994.Google Scholar
Man, H., Rabaey, J., Vanhoof, J., et al., CATHEDRAL-II-a computer-aided synthesis system for digital signal processing VLSI systems, Computer-Aided Engineering Journal, 5, 55–66, 1988.CrossRefGoogle Scholar
Peymandoust, A. and Micheli, G. D., Using symbolic algebra in algorithmic level DSP synthesis, Design Automation Conference, Las Vegas, 2001. New York, NY: ACM, 2001.Google Scholar
Peymandoust, A., Simunic, T., and Michell, G. D., Low power embedded software optimization using sumbolic algebra, Design Automation and Test in Europe, Paris, 2002, pp. 1052–1058. Washington DC: IEEE Computer Society, 2002.Google Scholar
Vincentelli, A. S., Wang, A., Brayton, R. K., and Rudell, R., MIS: multiple level logic optimization system, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 6, 1062–81, 1987.Google Scholar
Brayton, R. K. and McMullen, C. T., The decomposition and factorization of Boolean expressions, International Symposium on Circuits and Systems, 1982. Washington, DC: IEEE Computer Society, 1982.Google Scholar
Rajski, J. and Vasudevamurthy, J., The testability-preserving concurrent decomposition and factorization of Boolean expressions, IEEE Transactions on Computer-Aided Design of Intergrated Circuits and Systems, 11, 778–793, 1992.CrossRefGoogle Scholar
Brayton, R. K., Rudell, R., Vincentelli, A. S., and Wang, A., Multi-level logic optimization and the rectangular covering problem, International Conference on Compute Aided Design, 1987, Los Amitos, CA: IEEE Computer Society Press, 1987.Google Scholar
Rudell, R., Logic synthesis for VLSI design, Ph.D. Thesis, University of California, Berkeley, 1989.
Embree, P. M., C Algorithms for Real-Time DSP. Upper Saddle River, NJ: Prentice Hall, 1995.Google Scholar
Sinha, A. and Chandrakasan, A. P., Jouletrack-a Web based tool for software energy profiling, Proceedings of the annual ACM IEEE Design Automation Conference, Las Vegas, June 2001. pp. 220–225. New York, NY: ACM, 2001.Google Scholar
Muchnick, S. S., Advanced Compiler Design and Implementation. San Francisco, CA. Morgan Kaufmann Publishers, 1997.Google Scholar
Hosangadi, A., Fallah, F., and Kastner, R., Factoring and eliminating common subexpressions, polynomial expressions, International Conference on Computer Aided Design [ICCAD], San Jose, 2004, pp. 169–174. Washington, DC: IEEE Computer Society, 2004.Google Scholar
Hosangadi, A., Fallah, F., and Kastner, R., Energy efficient hardware synthesis in polynomial expressions, International Conference on VLSI Design, Kolkata, India, 2005. pp. 653–58. Washington, DC: IEEE Computer Society.
Potkonjak, M., Srivastava, M. B., and Chandrakasan, A. P., Multiple constant multiplactions: efficient and versatile framework and algorithms for exploring common subexpression elimination, IEEE Transactions on Computer Aided Design of Intergrated Circuits and Systems, 15(2), 151–65, 1996.CrossRefGoogle Scholar
Hosangadi, A., Fallah, F., and Kastner, R., Common subexpression involoving multiple variables for linear DSP synthesis, IEEE International Conference on Application Specific Architectures and Processors (ASAP), Galveston, 2004. Washington, DC: IEEE Computer Society, 2004.Google Scholar
Hosangadi, A., Fallah, F., and Kastner, R., Reducing hardware compleity of linear DSP systems by interatively eliminating two term common subexpressions, Asia South Pacific Design Automation Conference, Shanghai, 2005. New York, NY: ACM, 2005.Google Scholar
Downey, P., Leong, B., and Sethi, R., Computing sequences with addition chains, SIAM Journal of Computing, 10, 638–46, 1981.CrossRefGoogle Scholar
Koyama, K., and Tsuruoka, T., Speeding up elliptic cryptosystems by using a signed binary window method, Proceedings of the 12th Annual International Cryptography Conference on Advances in Cryptography, Santa Barbara, August, 1992, pp. 345–47. London: Springer Verlag, 1992.Google Scholar
Flores, P. F., Monteiro, J. C., and Costa, E. C., An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications, International Conference on Computer Aided Design (ICCAD), San Jose, 2005. Washington, DC: IEEE Computer Society, 2005.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Polynomial expressions
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.007
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Polynomial expressions
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.007
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Polynomial expressions
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.007
Available formats
×