Millepede: Linear Least Squares Fits with a Large Number of Parameters

In certain least squares fit problems with a very large number of parameters the set of parameters can be divided into two classes, global and local parameters. Local parameters are those parameters which are present only in subsets of the data. Detector alignment and calibration based on track measurements is one of the problems, where the interest is in optimal values of the global parameters. A method to solve the linear least square problem for the global parameters, irrespectively of the number of local parameters, has been developed, called Millepede. The method is a general linear-least-square method, i.e. not directly related to e.g. alignment of track detectors.

The Millepede Principle

The straightforward application of the least squares method for the simultaneous fit of e.g. 1000 global (alignment) parameters and of e.g. 1 Million tracks, each parametrized with 5 local (track) parameters, would result in normal equations with a 5 001 000 x 5 001 000 matrix. Present day computers are not able to solve such large systems. However the large matrix has a special structure. In the Millepede Principle a partitioning of submatrices, based on this structure, is used to include all information from all local (track) fits in the 1 000 x 1 000 matrix of global parameters. The matrix equation with this matrix is solved in Millepede I by inversion; the inverse matrix is the covariance matrix of the global parameters. The solution for the global parameter corresponds to the large simultaneous fit mentioned above; it is not an approximation. The Millepede Principle allows to solve a huge problem in one step, without iterations (unless there are other reasons to perform iterations). A conference contribution on the Millepede Principle for track-based alignment was made to the 1997 CHEP conference in Berlin, organized by Deutsches Elektronen-Synchrotron (DESY), but not accepted. A second program version, Millepede II, has been developed since 2005, which allows to have more than 5 000 parameters; it has already been used for up to 50 000 parameters. It includes several different methods for the solution of large systems of equations (see below).

Millepede II is, like Millepede I, a general, experiment-independent program. No part of the code is specific for track-based alignment. Both versions allow to specify equality constraints between global parameters.

Millepede I

Development started in the year 1996 for a version with a practical limit for the number of global parameters between one thousand and ten thousand. It is used regularly since 1997 for various alignment problems in the H1 detector. This version, now called Millepede I, is available on the web since the year 2000. The last change made in year 2000 was to replace a general matrix multiplication routine by a special routine for sparse matrices. No changes were made since then.
It has been used and is still used by several experiments. e.g. H1, ZEUS, HERAb, CMS, LHCb, Alice, PHENIX, STAR ... It has been rewritten in C++ several times.

Year-2000 version: psfile

The software can be freely used for research and education. We expect that all publications describing work using this software quote at least one reference.

Disclaimer: This software is provided without any expressed or implied warranty. In particular there is no warranty of any kind concerning the fitness of this software for any particular purpose.

Year-2000 program code: source file



Millepede II

A new development, called Millepede II, started in the year 2005 with the aim to allow of the order of hundred thousand global parameters. This number corresponds to requirements of LHC experiments for their track-based alignment.

Millepede II has two parts. A small subroutine MILLE is used in the user programs to write files with the data (measurements or residuals, derivatives etc.). These data files together with steering text files are input to the stand-alone program PEDE, which performs the calculations and finally writes text files with the results. In order to cope with the much larger number on parameters wrt Millepede I, there are several options.

Methods of matrix storage:
  1. symmetric matrix with (n*n+n)/2 elements;
  2. symmetric sparse matrix with n + q * (n*n-n)/2 elements (+ pointer array), if fraction q of the off-diagonal elements is non-zero;
  3. variable-band matrix with m*n elements.
Additional matrix space is needed for the equality constraints.

Solution methods of the matrix equation:
  1. matrix inversion by Gauss elimination;
  2. Cholesky decomposition of a symmetric matrix;
  3. matrix diagonalization (Householder method) with determination of eigenvalues and eigenvectors (requirement of a n*n matrix in addition);
  4. Cholesky decomposition of a variable-band matrix;
  5. GMRES - generalized minimization of residuals;
  6. GMRES - generalized minimization of residuals with preconditioning by Cholesky decomposition of a variable-band matrix.
In an investigation of the alignment of the full central track detector of the cms experiment (see Talk by Markus Stoye, given below) the following parameters were used:

Status: The Millepede II code is under test in cms and in H1. The comparison of results from H1 between Millepede I and Millepede II has shown only small differences in the parameters in the order of percent of the statistical error, if outlier treatment is selected for Millepede I and II. The outlier treatment is slightly different in the two versions.

Manual and program code are preliminary!

Millepede II: The Manual

The software can be freely used for research and education. We expect that all publications describing work using this software quote at least one reference.

Millepede II: The program code

Expand the code, compile/link and execute test by:

Disclaimer: This software is provided without any expressed or implied warranty. In particular there is no warranty of any kind concerning the fitness of this software for any particular purpose.

Talks

A new method for the high-precision alignment of track detectors, Volker Blobel and Claus Kleinwort, Conference on Adcanced Statistical Techniques in Particle Physics, Durham, 18 - 22 March 2002
ps-file

Software Alignment for Tracking Detectors: Seminar Datenverarbeitung in der Hochenergiephysik - Computing in High Energy Physics, DESY Seminar, 17th January 2005 Talk

Software Alignment for Track Detectors, Workshop on Tracking in high Multiplicity Environments, Zürich, 3rd - 7th October 2005 Talk

Detector Alignment by Tracks with Millepede II: ATLAS Inner Detector Alignment and Commissioning Workshop, Schloss Ringberg, June 13.th 2006 Talk

Alignment Algorithms: LHC Detector Alignment Workshop, September 4 - 6 2006, CERN Talk

Alignment of track detectors - Large scale optimization: DESY Computing seminar, May 14th, 2007, DESY Talk


Status and Prospects of Millepede II: CMS Tracker alignment workshop, May 29th, 2007, Hamburg Talk


Millepede II: 2nd LHC detector alignment worklshop, June 25th and 26th, 2007, CERN Talk


A talk on the use of Millepede II for the cms tracker:

A Global CMS-Tracker Alignment Study, Markus Stoye (with Gero Flucke, Georg Steinbrück, Peter Schleper), DPG Tagung in Heidelberg, March 8, 2007
Talk

Papers

A new method for the high-precision alignment of track detectors, Volker Blobel and Claus Kleinwort, Contribution to the Conference on Adcanced Statistical Techniques in Particle Physics, Durham, 18 - 22 March 2002 psfile

A New Method for the High-Precision Alignment of Track Detectors, Volker Blobel and Claus Kleinwort, Proceedings of the Conference on Adcanced Statistical Techniques in Particle Physics, Durham, 18 - 22 March 2002, Report DESY 02-077 (June 2002) ps-file and hep-ex/0208021 pdf-file


Software Alignment for Track Detectors, Proceedings of the Workshop on Tracking in high Multiplicity Environments, Zürich, 3rd - 7th October 2005 pdf-file

See also: Nuclear Instruments and Methods A, 566 (October 2006), pp. 5-13

Alignment Algorithms, Proceedings of the LHC Detector Alignment Workshop, September 4 - 6 2006, CERN pdf-file