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.

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.

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.

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.

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.

- symmetric matrix with (n*n+n)/2 elements;
- symmetric sparse matrix with n + q * (n*n-n)/2 elements (+ pointer array), if fraction q of the off-diagonal elements is non-zero;
- variable-band matrix with m*n elements.

- matrix inversion by Gauss elimination;
- Cholesky decomposition of a symmetric matrix;
- matrix diagonalization (Householder method) with determination of eigenvalues and eigenvectors (requirement of a n*n matrix in addition);
- Cholesky decomposition of a variable-band matrix;
- GMRES - generalized minimization of residuals;
- GMRES - generalized minimization of residuals with preconditioning by Cholesky decomposition of a variable-band matrix.

- 50 000 parameters
- 130 equality constraints
- 3 Million tracks
- sparse matrix with total 2 Gbytes (full symmetric matrix would be 8 Gbytes)
- outlier down-weighting/rejection in local fits
- solution by GMRES with preconditioning (variable-band matrix)
- cpu-time 1 hour 40 minutes on 64-bit LINUX system

**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.

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

- tar -xzf Mptwo.tgz
- make
- ./pede -t

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.

ps-file

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

Talk

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