Comparing high-order multivariate AD methods. (2nd November 2018)

• Record Type: Journal Article
• Authors: Neidinger, Richard D.; Altman, Benjamin
• Is Part Of: Optimization methods and software. Volume 33:Number 4/6(2018)
• Page Start: 995
• Page End: 1009
• Publication Date: 2018-11-02
• Subjects: Differentiation -- high order -- multivariate -- series -- interpolation -- forward; 65D25 -- 65Y20 -- 65D05 -- 41A63 -- 41A05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1472256
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: To compute every high-order multivariate derivative value, interpolation methods will be shown to be less accurate than a direct forward multivariate Taylor series method, becoming significant for degrees higher than 10. As order increases, interpolation methods rely on increasingly ill-conditioned matrices where simply rounding exact rational values produced corresponding error in some resulting derivative values. Both interpolation and direct methods use forward AD (algorithmic differentiation); the direct method propagates multivariate series coefficients of the original function, while interpolation methods propagate univariate series of the function in fixed directions and reconstruct the multivariate values. Such interpolation methods, differing in direction choices and reconstruction methods, have been shown to be theoretically more efficient than the direct method for high order. Four alternatives were implemented in MATLAB (interpreted and using random access arrays) on the same laptop. In our implementations, the direct method was competitive and often faster in run time, in addition to maintaining good accuracy. Since AD tools in compiled languages are much faster, more comparison is needed. Direct method efficiency depends on indexing subsets within the large non-rectangular data structure for multivariate series coefficients. We explain key implementation details of our direct method that uses a global reference array.