Sunday, March 24, 2013

Benchmarks on matrix multiplication

I have been tuning for performance the matrix library, specially matrix multiplication. I have been using the well-known Strassen's algorithm to achieve sub-cubic complexity, but extending with zeroes the matrix to the next power of two order to match the hypothesis of the algorithm. Obviously, this method didn't work very well, but I took it as a starting point. From this point, my idea was to mix the standard multiplication with Strassen's idea, and to not expand the matrix unnecessarily.

After some work, I ended up extending the matrix to a square matrix of the next even order. Then apply one iteration of Strassen's algorithm. This process is iterated until certain order. Smaller matrices to this fixed order are multiplied using the definition. I have tried different switcher orders and benchmarking to see what's the best choice. These are benchmarks using switcher order k = 150. To understand it, note that multN means multiplication of square matrices of order N and that Definition and Strassen mixed mean that the multiplication has been done by definition or using my mixed algorithm respectively.

This benchmark table is hosted here.

Both take a very similar time for small entries, but, as the matrix grows, the difference gets bigger and bigger in favor of the mixed algorithm. This is a nice result that will be applied in the next release of matrix (0.2).

Tuesday, March 19, 2013

HaTeX 3.5

It's time for a new release of HaTeX!

The following changes have been made since the last release:

  • Fixed some minor bugs.
  • Remake of the parser, now using attoparsec instead of parsec. Also more correct and tested. Thanks to Tobias Schoofs for his contributions.
  • Extension of the AMSMath module. Thanks to leftaroundabout for his contributions.
  • Applicative instance for LaTeXT.
  • New functions for rendering matrices. This includes a new dependency in the matrix package.
  • And some other minor changes.

A complete list of changes can be found at the commit history. The new version is up in Hackage so update yours!

Sunday, March 17, 2013

Writing a new library: Wavy

I have two proposals for this Spring Break.
  • Release the version 3.5 of HaTeX.
  • End up the first layer of my new library: Wavy.

HaTeX 3.5

HaTeX has been in stand-by for a while now and I want to upload a version of HaTeX that at least contains the changes I have made so far. Hopefully, I will add some new features. I am thinking about a matrix writer, since is a pain to write matrices right now. If you take a look to the last changes on github, better support for math typesetting has been added thanks to leftaroundabout. He is (or has been) also writing an extension for HaTeX to make math typesetting more sophisticated. Also, toschoo has improved the parser and now it uses attoparsec. These are good news for HaTeX.


In the other hand, I am writing a new library. Its name is Wavy. It is a super kool library that read, writes and manipulates sounds very nicely. Yes, I know, lot of libraries have been written doing exactly the same. Exactly the same? Well, I think they are all different in some sense, and this is just another new approach. If it is going to be a better or worse approach is something I don't care, as long as is useful to somebody. And I already find it useful for myself! Although, of course, it would be great if somebody else find it interesting, so I will do my best to make of Wavy a nice library. To begin with, I started writing a user manual. I think is looking pretty good, but that is something that Haskell users should decide in my place. As an extension, I wrote a library that writes sound waves in PDFs. So yes, I am having a lot of fun! And it's everything written in Haskell!

I hope to have something more mature to show after the Spring Break, but I think is moment to start sharing this thoughts with the community. Below is a code example that shows Wavy in action writing a sine wave in a .wav file.

import Data.Sound
import Data.Sound.WAVE

main :: IO ()
main = encodeFile "sine.wav" $ fromSound 16 s
  s = sine 5 1 100 0