Approximation of function evaluation over sequence arguments via specialized data structures

• A warped grid data structure to retrieve stored approximate function evaluations.
• Saves computing first Taylor partials by using single gradient of warped surface.
• Applicable where function evaluation has lesser impact on greater arguments.
• Efficient single-lookup-indexing for any stored evaluation.
• Later application of interpolation to approximate any neighboring sequence.

This paper proposes strategies for maintaining a database of computational results of functions f   on sequence arguments x→, where x→ is sorted in non-decreasing order and f(x→) has greatest dependence on the first few terms of x→. This scenario applies also to symmetric functions f  , where the partial derivatives approach zero as the corresponding component value increases. The goal is to pre-compute exact values f(u→) on a tight enough net of sequence arguments, so that given any other sequence x→, a neighboring sequence u→ in the net giving a close approximation can be efficiently found. Our scheme avoids pre-computing the more-numerous partial-derivative values. It employs a new data structure that combines ideas of a trie and an array implementation of a heap, representing grid values compactly in the array, yet still allowing access by a single index lookup rather than pointer jumping. We demonstrate good size/approximation performance in a natural application.