This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

• Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
• Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
• Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
• Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
• Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
• Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf, which however are not self-explanatory due to my minimum-text presentation style.

The implementation is a single file C++ program, which can optionally output LaTeX code for debugging purposes. The code can easily be compiled on any Linux machine, and probably also using other tool chains. It requires the GNU mpfr library for arbitrary precision floating-point numbers to enable high precision calculations (this library is also available for Visual C++). You can download the clipper.zip (23 KB) and view the corresponding doxygen HTML documentation.

The program can output LaTeX code documenting each individual steps of the computation while it is running, this method yields extremely detailed execution protocols for each input. For demonstration purposes the code contains nine different sets of examples, called demo1 through demo9. Among these demos six, seven and eight are speed test demos, which can be run without debugging overhead to measure the algorithms' run time. Results of these speed tests are documented in the short report above. The detailed execution protocols of the eight demos can downloaded below:

• demo1.pdf (345 KB) - Simple demonstration using a polynomial of 5th degree
• demo2.pdf (561 KB) - Polynomial of 8th degree with many roots in [0,1]
• demo3.pdf (2.7 MB) - Wilkinson polynomial with n = 20
• demo4.pdf (269 KB) - Unspecified demo to test other polynomials
• demo5.pdf (288 KB) - All degree reduction and raising matrices for degree five
• demo6.pdf (6.4 MB) - Speed test of polynomials with one single root
• demo7.pdf (70.9 MB) - Speed test of polynomials with a triple root (Warning: very large PDF)
• demo8.pdf (5.3 MB) - Speed test of polynomials with two near single roots

[1] Bartoň, M. and Jüttler, B. "Computing roots of polynomials by quadratic clipping", Computer Aided Geometric Design 24.3, (2007) p. 125-141. DOI: 10.1016/j.cagd.2007.01.003

[2] Liu, L., Zhang, L., Lin, B., Wang, G. "Fast approach for computing roots of polynomials using cubic clipping", Computer Aided Geometric Design 26.5, (2009), p. 524-599. DOI: 10.1016/j.cagd.2009.02.003

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf (2,8 MB)

After four years I have decided to release an updated version 0.8.6 of the STX B+ Tree C++ Template Classes package. The updated release contains all patches that have accumulated in my inbox over the years. So yes, please send me patches for this project, it is not in vain! Below the highlights on the changes in this release:

• Implemented a missing function: erase(iterator iter) by recursively searching for the referenced leaf node inside the subtree containing equal keys.
• Applied a patch which adds support for STL allocators as template parameters.
• Corrected limits of a for loop when shifting pairs from left to right leaf nodes during deletion.

I also reran the speed test done back in 2007 on my new hardware and compared the results with the old data. Due to the larger L2 cache sizes in my new Intel Core i7, the B-tree speed-up first starts to show at about 100,000 integer items, rather than 16,000 items with my older Pentium 4. This might also have something to do with the new CPU using 64-bit pointers and thus requiring larger nodes for child references. Read the complete speed test here.

The updated source code package is available for download from this webpage.

This is yet another release entry of digup. This time, however, it is a major release with lots of new improvements and some old fixes:

• Added new flags --modify-window=number to allow larger deltas in the modification time of files. This is a fixup for checking backups copied onto FAT filesystems, because these store the time stamp with a precision of only 2 seconds. Since this is a common operation, the shortcut -w/--windows will set the allowed modification window to 1.
• Also added a new flag --exclude-marker=file, which makes the recursive file system walk skip all directories (and their sub-directories) containing a special marker file usually called .nobackup in other programs. This option is persistent and stored in the created digest file, so it must only be specified once and then in all subsequent runs the same directory marker is used to selectively skip over special directories.
• Added a --restrict=pattern temporary exclusion flag. If specified, all paths containing the pattern as a substring are temporarily skipped. This allows one to quickly check a specific folder or file structure for modifications. Especially useful in combination with -c to perform a full digest check on only a subset of the files.
• One more smaller fixup: using 64-bit file offsets on Window, which allows files larger than 2GB to work correctly.

For more information and the new version see the digup web page.

Fixed another severe bug in the digup tool: on the amd64 architecture the tool crashed when writing the digest file, thanks goes to Daniel D. for reporting and fixing this bug.

The bug was caused by the variable arguments lists va_list used twice in the fprintfcrc() function. Apparently, on the amd64 platform va_start() and va_end() must be called twice even when passed the list to vsprintf().

For more information and the new version see the digup web page.

Fixed a two bugs in the digup tool: added large file support when compiling the program and fixed a string allocation bug.

This new version enables large file support by using long long variables for size. Furthermore, a string allocation bug was fixed which occured when using -t and -f command line parameters.

For more information and the new version see the digup web page.

Fixed a small bug in the stx-execpipe library: add large file support when compiling the library.

This bug switches on the large file support functions. Without this fix a pipeline reading or writing files >2GB will not function properly. The fix is to #define _FILE_OFFSET_BITS 64 when compiling the library's code.

For more information and the source code see the stx-execpipe web page.

The STX C++ library series has been extended today with a new installation: the STX Execution Pipe library, in short STX ExecPipe. It is the solution to an issue that I encountered in writing a small backup application. This backup tool collects some file to backup and then calls tar and xz followed by ncftpput.

However, I could not find any useful C++ library that allows convenient chaining of external programs like used in everyday shell piping. This pipe line functionality is based on the system calls fork(), exec() and pipe(), which are not easy to use correctly. After writing some ad-hoc functions to call one or two external programs, I decided to tackle this basic problem once and for all. The result is the stx-execpipe library.

Using the library a C++ program can build a sequence of external programs with command line parameters. These programs are connected by the library just like a shell pipe: stdout of the preceding stage goes into stdin of the next one. The input and output of the whole pipeline can be redirected to a plain fd, a file or saved in a std::string.

One very interesting feature of the library is to insert intermediate processing functions into a pipe line. The data can be intercepted and passed back to the parent process for manipulation or just inspection. This was necessary to calculate the SHA1 digest of a backup tarball simultaneously to uploading it.

For more information and the source code see the stx-execpipe web page.

The following small code snippet exemplifies the flexibility of the stx-execpipe solution:

Published yet another C++ template library using a B-tree. This time the solution is a disk-based read-only key-value mapping using a "packed, sequential" B-tree as index structure.

All applications mapping a large number of constant, integral keys to string or data blobs can benefit from this library. The database structure is highly compact and contains self-verification checksums over both key and value areas.

stx-cbtreedb is a direct contender with cdb and tinycdb, which however are based on hash tables and do not retain key proximity. Compared to other full-fledged B-tree implementations like BerkeleyDB or TokyoCabinet, the stx-cbtreedb is very small, faster and the database files have much less overhead due to read-only optimizations.

For more information and the source code see the stx-cbtreedb web page.

My second LibriVox recording is finished! The basic idea behind LibriVox is to read public domain texts and to put the recordings back into the public domain. More about that on librivox.org.

As with the last recording, my personal motivation is to practice my rusty English pronunciation. By reading and rereading the texts I believe my English will become more fluent and in the end also achieve better articulation.

The second recording is "Double Take" by Richard Wilson, a science fiction short story available from Project Gutenberg. I have also made a quick LaTeX typesetted version of the Gutenberg etext for more comfortable reading and with slight corrections: doubletake_wilson_text.pdf (369 KB).

Story Summary / Teaser

Pacing through a high-speed spy adventure, young Paul Asher finds himself going around in circles -- very peculiar circles indeed!

Audio Recording - Runtime: 26:29

MP3 encoded with standard lame VBR preset (obviously better/smaller than CBR 128 kbps)

doubletake_wilson_tb_vbr.mp3 (19.1 MB)

The recording is now also available on archive.org in the LibriVox Short Science Fiction Collection 033.