Mathematical Foundations of Programming

Article # 16_2018

24 p.

PDF

submitted on 05th Oct 2018 displayed on website on 14th Nov 2018

S. V. Znamenskij
Numerical evaluation of the interpolation accuracy of simple elementary functions

Comparison of the accuracy of the restoration of elementary functions by the values in the nodes was made for algorithms of low-degree piecewise-polynomial interpolation. The test results clearly demonstrate in graphical form the advantages and disadvantages of the widely used cubic interpolation splines.
The comparison revealed that, contrary to popular belief, the smoothness of the interpolant is not directly related to the accuracy of the approximation. In the 20 disparate examples considered, the piecewise quadratic interpolation is rarely and only slightly inferior in the form of the used classical cubic splines, often by orders of magnitude better than many of them.
In several examples the high interpolation error of simple functions on a fixed grid appears to be almost independent of the degree of the algorithm and the smoothness of the interpolant. The piecewise-linear interpolation unexpectally appeared the most accurate in one of examples.
A new problem is presented: to find a local interpolation algorithm, exactly restoring any rational functions of the second order. (In Russian).

Key words: local interpolation, spline interpolation, convexity preserving, recovery precision. 2010 Mathematics Subject Classification: 65D05; 65D07, 68W99.

article citation

DOI

Article # 36_2018

16 p.

PDF

submitted on 25th Nov 2018 displayed on website on 30th Dec 2018

Arkady Klimov
Towards automatic generation of stencil programs with enhanced temporal locality

Stencil algorithms are widely used in areas of mathematical modeling on regular grids, the evolution of cellular automata (such as the game “life”), image processing, sequence analysis, etc. Such algorithms are well parallelized, but the usual approaches to parallelization have low temporal locality, which limits their scalability. It is possible to get rid of this drawback by using different re-ordering schemes for processing points, when the space is divided into small areas that fit into the cache, in which it is possible to advance by several iterations at once. However, such schemes are difficult to program and debug. There is a simple pyramid method, but it doesn’t scale well due to some duplication of calculations. Our approach is to use more sophisticated reordering schemes without duplication, for which code can be generated automatically from a relatively simple scheme specification. In this case, the schemes themselves are defined by specifying distribution functions that distribute the computational points over space and time. This article outlines the approach and considers, for a sample source, various code variants generated from different distribution functions. (In Russian).

Key words: stencil algorithms, parallel computing, automatic parallelization, temporal locality, pyramid method, dataflow computation model, placement, scheduling.

article citation

DOI

Article # 38_2018

18 p.

PDF

submitted on 17th April 2018 displayed on website on 28th Dec 2018

S. V. Znamenskij
Stable assessment of the quality of similarity algorithms of character strings and their normalizations

The choice of search tools for hidden commonality in the data of a new nature requires stable and reproducible comparative assessments of the quality of abstract algorithms for the proximity of symbol strings. Conventional estimates based on artificially generated or manually labeled tests vary significantly, rather evaluating the method of this artificial generation with respect to similarity algorithms, and estimates based on user data cannot be accurately reproduced.
A simple, transparent, objective and reproducible numerical quality assessment of a string metric. Parallel texts of book translations in different languages are used. The quality of a measure is estimated by the percentage of errors in possible different tries of determining the translation of a given paragraph among two paragraphs of a book in another language, one of which is actually a translation. The stability of assessments is verified by independence from the choice of a book and a pair of languages.
The numerical experiment steadily ranked by quality algorithms for abstract character string comparisons and showed a strong dependence on the choice of normalization.

Key words: string similarity, data analysis, similarity metric, distance metric, numeric evaluation, quality assessment.

article citation

DOI