Entries by Clifford Wolf

Some of the stuff I did in 2015:

Yosys now has a powerful formal verification flow based around the SMT2 file format: yosys-smtbmc. I've also made a presentation on computational complexity, SAT/SMT solving, and that new verification flow: http://www.clifford.at/papers/2015/yosys-smt-bmc/

I have written a documentation of the iCE40 bit-stream format and created a Yosys-based open source synthesis flow for that FPGA family (Project IceStorm): http://www.clifford.at/icestorm/

I have created PicoRV32, one of the smallest RISC-V CPU cores out there: https://github.com/cliffordwolf/picorv32

I've released SimpleVOut, A Simple FPGA Core for Creating VGA/DVI/HDMI/OpenLDI Signals: https://github.com/cliffordwolf/SimpleVOut

I have participated in this years Google Summer of Code as a mentor. Unfortunately the student I mentored dropped out shortly after the midterms. But the publicity from the Google Summer of Code helped me find Cotton Seed and some other very interesting people (or rather helped them find me). Cotton is the author of Arachne-pnr, the place and route tool used in the IceStorm FPGA flow.

I bought a Ninebot One, learned how to ride it, and then learned the hard way to only ride it wearing protective gear: I broke both my wrists and my right elbow in an accident. Luckily I recovered very quickly.

The video recordings on the (german) electronics lectures I gave at Metalab went online this year, over 100 videos : https://metalab.at/wiki/Elektronik_Kurs#Videoaufzeichnung

For Yosys I was long stuck with std::set<> and std::map<> as primary container classes because one of the goals of Yosys is to produce identical outputs for the same input across all compilers and architectures. (A goal that is not reached yet btw, but I'm working towards it.) The std::unordered_* versions of those containers don't even make guarantees about identical order of iteration between two processes executing the same code. For my taste it is to easy to make a crucial programming mistake and accidentally iterate over one of those containers in a situation where the order of iteration has a subtle influence on the program output. So I've created my own containers that have the guarantees I need for Yosys. My hashlib::dict<> is a replacement for std::unordered_map<> and my hashlib::pool<> is a replacement for std::unordered_set<>. (My containers also require the programmer to be more explicit when using pointers as keys and they utilize an interface for creating hash values that integrates better with Yosys's core data structures than the std::hash()-scheme does.)

To my surprise my straight-forward textbook implementation of a hash table is significantly -- sometimes over 2x (!) -- faster than the STL versions of the same containers. I guess it pays off if you do not design your data structures around strange interfaces such as bucket iterators.. (Did anyone ever use them, btw?)

The picture below shows the results of this simple benchmark (also includes my hashlib.h library). Because I replace the ordered STL containers directly with my unordered versions, I also included the ordered STL containers in the benchmark. The labels "sparse" and "dense" in the figures below refer to the used alphabet. The "dense" alphabets are slightly easier to hash. For each of the 240 data points the benchmark executed 20000000 operations (insert, update or delete), first filling the container to the specified size (in number of elements) and then inserting and deleting while keeping the size around that value (within +/- 1000 entries and +/- 10%). In the tests for the map containers int was used as value type. (click image to enlarge)



PS: Clang version: 3.4-1ubuntu3, GCC version: 4.8.2-19ubuntu1

I bought an Acer Chromebook 13 CB5-311-T6R7 (the one with the NVidia Tegra K1 ARM CPU) to run it in a dual-boot configuration with Chrome OS and Ubuntu. I've used a slightly modified version of the modified chrubuntu script from here to install ubuntu. My version of the scripts and a writeup of the install procedure can be found here.

Update 2015-01-20: I have now updated my install script to address the freeze up issue discussed in the comments below. See my comment for the details of the fix used.

Update 2015-08-28: I have now updated my install script to use the current NVidia "Tegra for Linux" release, Tegra124_Linux_R21.4.0.

After over 8 years of service my old server had a fatal crash three days ago. The disk controller died and killed both disks (RAID1) in the process. Fortunately my backup strategy worked like a charm and I only lost about 6 hours of incoming email (so if you sent me a mail in the morning of Thu 4th December 2014: please try again).

Following an ancient tradition (of over 15 years) the new server is called phoenix.clifford.at, like the ones before it.

I have a backup of all data from the old machine, but I decided not to re-setup everything that ran on the old server. Especially I did not re-setup the shell logins I gave away over the course of the last 15 years. I also decided not to re-setup the services related to ROCK Linux. Please contact me if you had data on the old server that you want back or had a shell account that you were still using..

BTW: The backup solution I'm using is a simple shell script I wrote over 10 years ago and am using ever since. I've now put it on github, just in case anyone of you is interested: https://github.com/cliffordwolf/rsbak3

I own a TomTom Start navigation system. A few weeks ago it suddenly stopped working: It simply would not power on. Yesterday I took it apart to see if there was something I could do to fix it, or harvest some parts if there was nothing I could do. I took it apart but left all components connected to each other, with the exception of the speaker which I had to unplug in order to get the electronics out of the case. Most of the electronics are behind a soldered shield and there where no visible faults on the parts that where freely accessible. So I started by measuring the supply voltage: The battery was still fully charged. At this point I had an idea: What if the TomTom, as many devices do these days, has a small microcontroller that is always powered on and handles stuff like the power-up sequence? What if this microcontroller got stuck? I simply unplugged the battery and plugged it back in. The device booted right away.

So if you have a TomTom and encounter such a problem: don't just throw it away. Instead try unconnecting and reconnecting the battery from the motherboard first. However: It might not be easy to take the device apart and reassemble it if you don't have experience with that kind of stuff. Just remember: You have nothing to loose. Hint: There is a screw hidden behind the hinge for the vacuum cup.

Remains one question: Is this really a bug or planned obsolescence? If done right, it is almost impossible to have such a crucial bug in such a simple microcontroller application. That's why microcontrollers usually have features such as brown-out detection and hardware watchdog timers: so that you can write firmware for them that never hangs, even if there is a critical bug in it or the supply voltage has crazy transients. So either they had extremely bad luck with this particular design, or they designed it to fail approximately one year after the first power-on.

I recently bought a RIGOL DS2072 Oscilloscope. This is not a review but let me just say this: For the price this scope is awesome!

Of course I want to control my new scope from Linux. There are some articles online how to talk to a DS1052E [1, 2], but I haven't found anything that can be applied directly to the DS2072. When I connect the DS2072 via USB with the PC, the scope gets enumerated as PTP (Picture Transfer Protocol, a USB protocol for cameras) device and I have not figured out how to put it in a different mode. But the DS2072 also has an ethernet port and I managed to interface with the scope via the VISA VXI Protocol using the LibreVISA library.

So I wrote a small command-line tool that provides a shell that accepts commands from the terminal, sends them to the scope, reads back the results, and prints then to the terminal. The sourcecode of the program can be downloaded (or checked out) from this Subversion link:

http://svn.clifford.at/handicraft/2013/rigol-ds2000-shell/

The README file contains some instructions on how to build it and an example session demonstrating various features of the program.

Very recently a licence key generator for this scopes was published [3]. I have also included an interface to this generator that allows for easy unlocking of features in such scopes. Just connect to the scope an type 'install dsa9' to convert to a DS2202 with all options enabled (all commands are case-insensitive):

$ ./rigol-ds2000-shell TCPIP::192.168.0.123::INSTR

Connected to RIGOL TECHNOLOGIES,DS2072,DS2A152701234,00.01.01.
Type 'help' for help.

DS2A152701234> INSTALL DSA9
*** serial: DS2A152701234
*** options: DSA9
*** lic1-code: 12345678901234
*** lic2-code: 56789012345678
*** target-code: 90123456789012345678901234567
*** ----------------------------------------------------
*** your-license-key: 8901234-5678901-2345678-9012345
*** ----------------------------------------------------
> :SYSTEM:OPTION:INSTALL 8901234567890123456789012345

Of course input redirection (< filename) can be used to read commands from a file. For example, the following command file sets up the scope, waits for a trigger and then downloads the recorded data (as 5 mio. data points) to an ascii file.

*RST
SLEEP 1

:CHANNEL1:PROBE 10
:CHANNEL1:OFFSET 0
:CHANNEL1:SCALE 0.5
:CHANNEL1:COUPLING AC
:CHANNEL2:DISPLAY OFF
:TIMEBASE:SCALE 1e-4
:ACQUIRE:MDEPTH 14000000
SLEEP 3

:SINGLE
WAIT

:WAVEFORM:MODE RAW
:WAVEFORM:POINTS 5000000
DOWNLOAD_TXT waveform.txt

The commands starting with * or : are SCPI commands as described in the DS2000 Programming Guide. The other commands are native rigol-ds2000-shell commands and are described in the output of the HELP command.

A possible usage scenario is to call rigol-ds2000-shell from another program (such as GNU Octave, SciLab, Matlab, R, Python, etc.) and read back the written files once rigol-ds2000-shell is finished. As downloading large waveforms usually takes a while, the overhead for calling a separate binary is negligible.

Another usage scenario is to use rigol-ds2000-shell interactively to figure out the correct command sequences and then write a custom tool for whatever you want to do with your scope, possibly reusing some of the code from rigol-ds2000-shell.

Ich werde in den kommenden zwei monaten jeweils einen LUGA Vortrag halten (Achtung: fuer die LUGA unueblich sind die Termine Donnerstags):

• Do, 23.5.2013 -- High-Performance-Computing mit GPUs
  
• Do, 27.6.2013 -- OpenSCAD und QCad/LibreCAD
  

Wie viele meiner Leser wissen werden halte ich im Metalab auch einen Elektronik Kurs zum dem schon laenger Videos versprochen sind. Diese koennten moeglicherweise bald online gehen. Wer nicht warten will kann sich durch folgende bunt gemischte Videoempfehlungen durchclicken:

• LLVM 2012 European Conference
  Insbesondere der "Tablegen Deep Dive" Vortrag von Reed Kotler hat mir besonders gefallen. Da wurden viele meiner lang anstehenden Fragen zu TableGen geklaert. Die Folien zum Workshop "Building a backend in 24 hours" von Anton Korobeynikov fand ich ebenfalls sehr aufschlussreich.
  
  
• LLVM 2012 US Conference
  Da kann ich besonders "MemorySanitizer, ThreadSanitizer" von Kostya Serebryany und "Zero-Cost Abstractions" von Chandler Carruth empfehlen.
  
  
• GTC on Demand
  Da sind so viele Videos zu GPU programmierung das es sehr schwierig ist die wirklich guten zu finden. Die Optimization Talks von Paulius Micikevicius sind ausgezeichnet. Und "Better Performance at Lower Occupancy" von Vasily Volkov ist quasi ein Klassiker. Die Videos von der GTC 2013 sollten bald online gehen (die GTC 2013 war von 18. bis 21. Maerz und lt. Website wollten sie die Videos nach 30 tagen online stellen).
  
  
• 29C3 - Not My Department
  Die Videos zum letzten chaos communication congress liegen auf media.ccc.de. Ich fand insbesondere den Vortrag zu Low-Cost Chip Mi­cro­prob­ing von dexter und nohl interessant. (Ich erspare euch jetzt mal das gejammer darueber, dass es am kongress zu wenig technische talks gibt.)
  

Falls jemand weitere Vortragsvideos empfehlen moechte freue ich mich ueber entsprechende Kommentare!

I'm back from 29C3 and it was awesome! Lessons learned for the next year:

• You can not escape the Hackerpest!
  


• Pack at least a full set of clothes for every day (including new trousers for every day), if you plan to spend even a second in the smokers area.


• Bring heavy shoes for walking around outside and light shoes for walking around at CCH.


• Have a look at the Workshop schedule beforehand and use a schedule app (or write one) that includes the workshops and other auxiliary events.


• Don't be such a geek and talk to more people and ask more questions at the assemblies.


• Bring more stuff if you have additional space in your case.


• Bring an extra bag to carry stuff around at the conference.


• If you can afford it, book a room at the Radisson Blu (the hotel directly connected to the CCH).


• Prepare yourself to explain all your ongoing projects in less than 5 minutes.


• Arrive at day 0 or even day -1.

(Bild: MagicShifter by Wizard23)

This is a quick write-up of the steps necessary to install Xilinx ISE 14.2 / Vivado 2012.2 on Kubuntu (Ubuntu) 12.04.1 LTS (64bit). First of all lets be said that Xilinx does not officially support Kubuntu/Ubuntu as Platform. It might work or not but don't blame Xilinx if it doesn't...

First of all extract the Xilinx_ISE_DS_Lin_14.2_P.28xd.3.0.tar and execute xsetup as root. Install everything in the default directory (/opt/Xilinx). This may take a while.

When you want to start ISE, Vivado or Vivado_HLS, first execute the command "source /opt/Xilinx/14.2/ISE_DS/settings64.sh" in your shell to set PATH and other environment variables. Note that the PATH set by this command does not include the PATH to docnav (/opt/Xilinx/DocNav/) and viavdo_hls (/opt/Xilinx/Vivado_HLS/2012.2/bin/). This commands still must be called using the full path. I'm not sure why Xilinx decided to not add this directories to the PATH environment variable.

Xilinx ISE comes with its own version of some system libraries (like libstdc++). The settings64.sh script adds the directories containing this libraries to the LD_LIBRARY_PATH environment variable. This has the effect that after you have sourced this script in your shell you can't exectue many system commands in this shell anymore. So I recomment working with two shells: One for the Xilinx commands and a 2nd one for the system commands.

The tools are using kfmclient, google-chrome and acroread to open web sites and display PDF files. I have neither command on my system and even if I had just calling them would not work as one would have to reset LD_LIBRARY_PATH in order to execute them. So I had to add some wrapper scripts that are calling the appropriate tools with a cleaned-up environment.

--- /usr/local/bin/kfmclient ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
echo "KFMCLIENT: $*" >&2
[ "$1" = openURL ] && chromium-browser "$2" &
exit 0

--- /usr/local/bin/google-chrome ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
chromium-browser "$@" &
exit 0

--- /usr/local/bin/acroread ---
#!/bin/bash
unset LD_LIBRARY_PATH
export PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
okular "$@" &
exit 0

(In case you are wondering: The ISE tools are using kfmclient to open web-pages and the Vivado tools are directly trying to call a web-browser executable. Vivado tries "google-chrome" first, followed by "firefox" and a short list of others.)

Of course one can also consider installing such wrapper scripts in one of the Xilinx bin directories. I've decided to install the directly in /usr/local/bin/ for various resons that might not apply to everyone..

In order to get Vivado_HLS running two additional steps are required. First we need to copy crt1.o, crti.o and crtn.o to a place where the gcc that comes with Vivado_HLS can find it:

sudo cp /usr/lib/x86_64-linux-gnu/crt[1in].o \
/opt/Xilinx/Vivado_HLS/2012.2/Linux_x86_64/tools/gcc/lib/gcc/

Unfortunately the SystemC C++ code generated by Vivado_HLS suffers from the so-called "c++ static initialization order fiasco" (just google the term if you are not familiar with it). To make it short: The SystemC code generated by Vivado_HLS depends on undefined C++ behavior which leads to strange problems on some platforms while others are not effected (depending on the initialization order of static objects in different compilation units). This is a serious problem and as of this writing I'm in contact with Xilinx support in order to resolve it.

Note that this Problem does not effect the generated Verilog and VHDL RTL code. It only effects the SystemC module that is generated for simulation purposes only.

I've recorded a short (2:41) screencast in which I demonstrate the problem and a possible solution (i.e. using the "sc_dt::Log_*" enum to initialize static variables instead of using the global "SC_LOGIC_*" objects):
http://www.youtube.com/watch?v=HqDpRUFff94

Another work-around is to change one of the SystemC headers so that every compilation unit gets its private version of the SC_LOGIC_* objects, thus resolving the initialization order problem (the initialization order of static objects within a compilation unit is defined in C++):

--- Vivado_HLS/2012.2/Linux_x86_64/tools/systemc/include/sysc/datatypes/bit/sc_logic.h
+++ Vivado_HLS/2012.2/Linux_x86_64/tools/systemc/include/sysc/datatypes/bit/sc_logic.h
@@ -593,10 +593,17 @@
 }
 
 
+#if 0
 extern const sc_logic SC_LOGIC_0;
 extern const sc_logic SC_LOGIC_1;
 extern const sc_logic SC_LOGIC_Z;
 extern const sc_logic SC_LOGIC_X;
+#else
+static const sc_logic SC_LOGIC_0 = Log_0;
+static const sc_logic SC_LOGIC_1 = Log_1;
+static const sc_logic SC_LOGIC_Z = Log_Z;
+static const sc_logic SC_LOGIC_X = Log_X;
+#endif
 
 // #ifdef SC_DT_DEPRECATED
 extern const sc_logic sc_logic_0;

This is of course the prefered solution if you want to get Vivado_HLS running as it does not require any changes to the generated SystemC modules. It is not a nice final solution. But it makes the whole thing work without somehow automatically patching all generated SystemC modules.

I haven't tried the cable drivers (I'm using my own software for JTAG programming) and certainly haven't tried all the tools that are part of Xilinx ISE 14.2 / Vivado 2012.2. But I think I've covered the most important topics in my tests and with the above hacks I have the parts I need for my work running just fine.

I hope this write-up is of help for some of my readers. Of course there is no warranty of any kind from my side and Xilinx does not support their software on Kubuntu/Ubuntu either. So don't say you have not been warned..

Morgen Abend, Fr. 30.3.2012 ab 19:00, startet der zweite Turnus des Metalab Elektronikkurs. In aller kuerze hier einfach noch mal ein copy&paste der Ankündigung:

Das Metalab (http://metalab.at/) veranstaltet einen kostenlosen
Elektronikkurs. Der erste Kursabend, der zugleich die Vorbesprechung zur
Koordination der weiteren Termine darstellt, findet am Freitag dem
30.3.2012 ab 19:00 im Metalab, Rathausstrasse 6, 1010 Wien statt.

Detailierte Informationen zu den Kursinhalten und zum Ablauf sowie eine
PDF-Version des Skriptums sind auf der Homepage des Kurses zu finden:

https://metalab.at/wiki/Elektronik_Kurs

Für diejenigen, die die Grundlagen schon beherrschen und sich primär für
die Fortgeschrittenen-Themen interessieren, ist auch ein späterer Einstieg
in den Kurs möglich. Der Besuch des ersten Kursabends ist aber wegen der
Vorbesprechung auf jeden Fall empfohlen.

Zielgruppe sind alle Menschen die sich für Elektronik interessieren und
elektronische Schaltungen verstehen und selbst entwickeln wollen.

Ich freue mich auf möglichst viele TeilnehmerInnen!

Nachdem ich gerade mein Android Handy neu aufsetzen musste hier eine kleine Liste von Android Apps die ich gut finde und auf meinem Handset installiert habe (neben Apps wie YouTube und Google Maps die schon Teil der Factory Defaults sind):

• AnkiDroid
  
• ConnectBot
  
• Barcode Scanner
  
• Google Goggles
  
• CamScanner
  
• Adobe Reader
  
• Google Reader
  
• TuneIn Radio
  
• Twitter
  

Und bis VLC for Android fertig ist verwende ich erst mal RockPlayer Lite.

Kommentare mit weiteren App-Empfehlungen sind natuerlich herzlich willkommen!

This American Life hat vor fast zwei Wochen die hervorragend gemachte Folge "When Patents Attack!" ausgestrahlt.

Ich erwaehne das hier weil die Folge ein Musterbeispiel dafuer ist, wie man einem nicht-technischen Publikum die ganze Patentproblematik (insbesondere im Zusammenhang mit Softwarepatenten) verstaendlich machen kann. Daher: Ein Muss sowohl fuer alle die gegen den Patentwahnsinn aktiv sind (als Anregung und Referenz) als auch (und insbesondere) natuerlich fuer jene die sich noch nicht so viele Gedanken zu dem Thema gemacht haben.

Besonders gut gefaellt mir, wie in der Sendung aufgezeigt wird, dass Patente in der Welt der tatsaechlich stattfindenden Ereignisse weder innovationstreibenden Firmen noch kleinen Erfindern nutzen, sondern nur einer aeusserst zweifelhaften Industrie von mafiahaft agierenden "Patent Trollen" dabei Hilft eben jene innovationstreibenden Firmen und kleine Erfinder zu terrorisieren.

Derart klar und unmissverstaendlich auf den Punkt gebracht sollte jede ernsthafte Ausseinandersetzung mit dem Thema sein.

Seit etwa eineinhalb Jahren beschaeftigt mich folgender Gedanke. Sicherlich ist der nicht grundlegend neu und daher habe ich mich entschlossen mal darueber zu bloggen. Moeglicherweise hat ja eine mathematisch bewanderte LeserIn einen Pointer zu weiteren Informationen zu dem Thema fuer mich ...

Zunaechst moechte ich den Begriff der "beschreibbaren Zahl" definieren:

Def. 1: Eine beschreibbare Zahl ist eine (reelle) Zahl die entweder ueber eine Beschreibung Ihrer Eigenschaften oder ueber eine Konstruktionsvorschrift innerhalb eines Zeichensystems eindeutig von allen anderen Zahlen unterschieden werden kann.

Man wuerde annehmen, dass alle (reellen) Zahlen in die Menge der beschreibbaren Zahlen fallen. Doch das scheint nicht der Fall zu sein.

Def. 2: Eine Aussage ist eine endliche Folge von Zeichen eines Zeichensystems aus einer endlichen Anzahl von Symbolen, die geeignet ist maximal eine abzaehlbar grosse Menge von konkreten Zahlen zu beschreiben. Z.B. koennte man als Zeichensystem einfach das ASCII-Alphabet und die deutsche Sprache verwenden.

Was ist gemeint mit "maximal eine abzaehlbar grosse Menge von konkreten Zahlen"? Damit ist gemeint, dass eine Aussage zwar z.B. die reellen Zahlen als Menge in ihrerer Gesamtheit beschreiben kann, nicht aber jedes Element eindeutig zu beschreiben vermag. (Selbst mit Auswahlaxiom koennte man wohl nur eine abzaehlbar grosse Teilmenge der reellen Zahlen in einer Aussage beschreiben. Wir wollen das Auswahlaxium aber nicht zulassen, sonst kaeme jemand auf die Idee ein Element aus Menge der nicht beschreibbaren Zahlen auszuwaehlen.) Ich hoffe dieser Sachverhalt ist anschaulich genug so dass er so akzeptiert werden kann.

Lemma 1: Es gibt eine abzaehlbar unendlich grosse Menge von Aussagen. Das folgt unmittelbar, da man jeder Nachricht {z_1, z_2, .. z_n} mit n Zeichen aus einem Zeichensystem aus k verschiedenen Zeichen die natuerliche Zahl sum(z_i * k^(i-1), i = 1..n) zuordenen kann. D.h. man kann z.B. jeder ASCII Datei eine sehr grosse Binaerzahl zuordnen.

Lemma 2: Es gibt eine abzaehlbar unendlich grosse Menge von beschreibbahren Zahlen. Das folgt unmittelbar wenn man Cantors erstes Diagonalargument auf die abzaehlbar unendlich grosse Menge von Aussagen und die abzaehlbar unendlich grosse Menge von beschreibbaren Zahlen pro Aussage anwendet.

D.h. dass es z.B. in der Menge der reellen Zahlen (die ja ueberabzaehlbar groß ist) eine abzaehlbar grosse Teilmenge von beschreibbaren Zahlen gibt zu der alle konkreten Zahlen gehoeren mit denen wir uns je beschaeftigen. Damit wir uns mit einer konkreten Zahl ueberhaupt beschaeftigen koennen muss sie ja beschreibbar sein. Der ueberabzaehlbar grosse Grossteil der reellen Zahlen aber besteht offenbar aus nicht beschreibbaren Zahlen die fuer uns als einzelne nicht greifbar sind. Es ist unmoeglich so eine Zahl aus den reellen Zahlen herauszureissen und als einzelne zu untersuchen.

This blows my mind! Was denkt Ihr?

In letzter Zeit habe ich einiges zu linear Algebra C Libraries recherchiert. Hier eine kurze Aufstellung der interessantesten Dinge die ich gefunden habe:

Zunaechst die Loesungen die ich bereits kannte:

GSL
Bis jetzt habe ich fast alles was mathematisch/numerisch anspruchsvoller war mit dieser library gemacht. Da findet man unter anderem auch funktionen fuer die wichtigsten algorithmen aus der linearen algebra. Leider hat GSL keinen support fuer sparse Matrizen. In meinem gegenwaertigen Projekt brauche ich aber genau das.

Eigen
Eine C++ Library fuer lineare Algebra. Wegen operator overloading und templates ist Eigen natuerlich einfacher zu verwenden als GSL. Der wesentliche Vorteil ist aber meiner meinung nach, dass man eigene Basistypen definieren kann. Wenn man also Matrizen ueber Koerper die nicht die reellen oder komplexen Zahlen sind bauen moechte ist Eigen sicherlich einen Blick wert. Ich bin ueber Eigen im Zuge der Entwicklung von OpenSCAD gestolpert und verwende es dort fuer die in der Geometrie ueblichen 2-4 dimensionalen Matrizen.

BLAS bzw. CBLAS
Die low-level API fuer lineare algebra. Es gibt viele implementierungen - unter anderem eine in GSL. Komplexere algorithmen wie etwa die verschiedenen Matrizenzerlegungen muss man sich selber bauen.


Im Zuge meiner recherchen bin ich dann unter anderem auf folgene Projekte gestossen:

SuiteSparse
Eine Sammlung kleinerer Libraries zum Arbeiten mit sparse matrizes. Ich verwende davon KLU, eine Library zum LU-Faktorisieren duenn besetzter sparse Matrizen und loesen der entsprechenden linearen Probleme.

PETSc
Eine groessere mathematik suite fuer MPI-basiertes parallel computing. Wurde mir von B. empfohlen. Ich hab mich aber nur ein bsichen auf der website umgesehen - fuer meine Anwendung schien mir das doch zu schwergewichtig zu sein.

SelInv
Ein recht interessantes paper von Lin Lin mit dem Titel "SelInv -- An algorithm for selected inversion of a sparse symmetric matrix". Fast genau das was ich eigentlich gesucht habe. Mal sehen wie gross meine Matrizen wirklich werden. Wenn ich mit KLU an die grenzen Stosse werde ich wohl versuchen etwas in dieser Richtung zu implementieren.


Habt Ihr noch Hinweise fuer mich (oder andere Leser) zu guten linear algebra libraries? Dann schreibt doch bitte ein Kommentar..

Zu meiner Anwendung: Ich versuche derzeit die Eigenschaften einzelner Zeilen der Inversen von bestimmten symetrischen sparse Matrizen (dimension etwa 50.000 - 250.000) zu untersuchen - freue mich aber auch ueber Hinweise auf Libraries und Tools die nicht auf dieses Problem passen.

Happy number crunching!

Ich schreibe ja recht viele Texte mit LaTeX. Kuerzlich hat A. folgendes Problem an mich herangetragen, dass ich nicht auf anhieb loesen konnte: Wurzeln sollten mit einem "Haken" hinten gesetzt werden, damit man eindeutig erkennen kann wo der Ausdruck unter der Wurzel endet.


W. aus Graz hat daraufhin folgendes Macro ausgegraben das offenbar schon seit einiger Zeit im Netz die Runde macht und den Job erledigt:

\def\hksqrt{\mathpalette\DHLhksqrt}
\def\DHLhksqrt#1#2{\setbox0=\hbox{$#1\sqrt{#2\,}$}\dimen0=\ht0
\advance\dimen0-0.2\ht0
\setbox2=\hbox{\vrule height\ht0 depth -\dimen0}%
{\box0\lower0.4pt\box2}}

Leider unterstuetzt diese Loesung keine Wurzeln belibiger Ordnung (wie die aussere Wurzel und die Wurzel im Zaehler in der Abbildung). Daher hab ich die o.g. Loesung etwas aufgebohrt so dass sie wie das LaTeX \sqrt Kommando die Ordnung der Wurzel als optionales Argument versteht:

\documentclass{article}

\newcommand\hksqrt[2][]{\mathpalette\DHLhksqrtA{{#1}{#2}}}
\def\DHLhksqrtA#1#2{\setbox0=\hbox{$#1\DHLhksqrtB#2$}\dimen0=\ht0
\advance\dimen0-0.2\ht0
%0.2 ist das Mass fuer die Hakenlaenge, relativ zum Inhalt der Wurzel
\setbox2=\hbox{\vrule height\ht0 depth -\dimen0}%
{\box0\lower0.4pt\box2}}
\def\DHLhksqrtB#1#2{\def\a{#1}\def\b{}\ifx\a\b\sqrt{#2\,}\else\sqrt[#1]{#2\,}\fi}

\begin{document}
Hier einige Wurzeln mit Haken:
\begin{equation}
c=\hksqrt{a^2+b^2}=\hksqrt[3]{\frac{\hksqrt[15]{x^2}-y}{y^2+\hksqrt{x+y}}}
\end{equation}
\end{document}

Vielleicht googelt ja mal jemand nach dem Problem und stolpert dann dabei ueber mein Blog..

PS: Morgen (Donnerstag, 29.4.2010) halte ich ab 19:00 im Metalab einen Vortrag ueber Graphiken mit LaTeX erstellen: http://www.luga.at/veranstaltungen/latex-2010-04-29/

PPS: Im Metalab gibt es ein regelmaessiges TeX/LaTeX Treffen: http://metalab.at/wiki/Leidensgruppe_LaTeX