NIK – Numerical analyzis and HPC

Author and abstract
Hans Jakob Rivertz and Ali Alsam: Fast color edge preserving smoothing
An edge preserving smoothing algorithm is presented. To prevent smoothing over edges, the algorithm requires that diffusion in a direction should not result in an increase in neighbouring gradients. Intuitively, we think that smoothing reduces gradients. This is, however, not true in the vicinity of strong edges where smoothing over the edge results in surface deformation. The possibility of reducing the calculation cost is explored by reducing the frequency of calculating the edge strength.
Tatiana Kravetc: Finite element method application of ERBS Triangles
In this paper we solve an eigenvalue problem on a circular membrane with fixed outer boundary by using a finite element method, where an element is represented as an expo-rational blending triangle. ERBS triangles combine properties of B-spline _nite elements and standard polynomial triangular elements. The overlapping of local triangles allows us to provide a exible handling of the surface while preserving the smoothness of the initial domain, also over the nodes and edges. Blending splines accurately approximate the outer boundary, while keeping a coarse discretization of the domain. We consider a mesh construction for such type of elements, evaluating of basis functions and their directional derivatives, local-to-global mapping, assembling of element matrices.
Hans Olofsen: Blending functions based on trigonometric and polynomial approximations of the Fabius function
Most simple blending functions are polynomials, while more advanced blending functions are, for example, rational or expo-rational fractions. The Fabius function has the required properties of a blending function, but is a nowhere analytic function and cannot be calculated exactly everywhere on the required domain. We present a new set of trigonometric and polynomial blending functions with the shape and other properties similar to the Fabius function. They consist of combinations of trigonometric polynomials and piecewise polynomials. The main advanced of these are that they are easy to implement, have low processing costs and have simple derivatives. This makes them very suitable for the calculation of splines. Due to the selfdifferential property of the Fabius function, scaled versions of these functions can even be used to approximate their own derivatives.
Arne Maus: RadixInsert, a much faster stable algorithm for sorting floating-point numbers
The problem addressed in this paper is that we want to sort an array a[] of n floating point numbers conforming to the IEEE 754 standard, both in the 64bit double precision and the 32bit single precision formats on a multi core computer with p real cores and shared memory (an ordinary PC). This we do by introducing a new stable, sorting algorithm, RadixInsert, both in a sequential version and with two parallel implementations. RadixInsert is tested on two different machines, a 2 core laptop and a 4 core desktop, outperforming the not stable Quicksort based algorithms from the Java library – both the sequential Arrays.sort() and a merge-based parallel version Arrays.parallelsort() for 500 The RadixInsert algorithm resembles in many ways the Shell sorting algorithm [1]. First, the array is pre-sorted to some degree – and in the case of Shell, Insertion sort is first used with long jumps and later shorter jumps along the array to ensure that small numbers end up near the start of the array and the larger ones towards the end. Finally, we perform a full insertion sort on the whole array to ensure correct sorting. RadixInsert first uses the ordinary right-to-left LSD Radix for sorting some left part of the floating-point numbers, then considered as integers. Finally, as with Shell sort, we perform a full Insertion sort on the whole array. This resembles in some ways a proposal by Sedgewick [10] for integer sorting and will be commented on later. The IEE754 standard was deliberately made such that positive floating-point numbers can be sorted as integers (both in the 32 and 64 bit format). The special case of a mix of positive and negative numbers is also handled in RadixInsert. One other main reason why Radix-sort is so well suited for this task is that the IEEE 754 standard normalizes numbers to the left side of the representation in a 64bit double or a 32bit float. The Radix algorithm will then in the same sorting on the leftmost bits in n floating-point numbers, sort both large and small numbers simultaneously. Finally, Radix is cache-friendly as it reads all its arrays left-to right with a small number of cache misses as a result, but writes them back in a different location in b[] in order to do the sorting. And thirdly, Radix-sort is a fast O(n) algorithm – faster than quicksort O(nlogn) or Shell sort O(n1.5). RadixInsert is in practice O(n), but as with Quicksort it might be possible to construct numbers where RadixInsert degenerates to an O(n2) algorithm. However, this worst case for RadixInsert was not found when sorting seven quite different distributions reported in this paper. Finally, the extra memory used by RadixInsert is n + some minor arrays whereas the sequential Quicksort in the Java library needs basically no extra memory. However, the merge based Arrays.parallelsort() in the Java library needs the same amount of n extra memory as RadixInsert.