کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435724 | 689930 | 2015 | 11 صفحه PDF | دانلود رایگان |
• 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.
Journal: Theoretical Computer Science - Volume 607, Part 1, 23 November 2015, Pages 113–123