Introduction

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 fits is one of the problems, where the interest is only in optimal values of the global parameters, the alignment parameters. The method, called Millepede, to solve the linear least squares problem with a simultaneous fit of all global and local parameters, irrespectively of the number of local parameters, is described in the draft manual. (Correlated measurements need to be transformed into independent measurements by diagonalization of their covariance matrix.)

The Millepede method and the initial implementation has been developed by V. Blobel from he University of Hamburg. Meanwhile the code is maintained at DESY by the statistics tools group of the analysis center of the Helmholtz Terascale alliance using GitLab (code and wiki).

The Millepede II software is provided by DESY under the terms of the LGPLv2 license.

Installation

To install Millepede (on a linux system):

Download the software package from the DESY gitlab server to target directory, e.g. (shallow clone):

 git clone --depth 1 --branch V04-16-01 \
     https://gitlab.desy.de/claus.kleinwort/millepede-ii.git target

Create Pede executable (in target directory):
```
 make pede
```
Optionally check the installation by running the simple test case:
```
 ./pede -t
```
This will create (and use) the necessary text and binary files.

Alternatively tarballs can be found here.

News

131008: New solution method MINRES-QLP [ref 9] implemented.
140226: Reading of C binary files containing doubles implemented.
141020: Storage of values read from text files as doubles implemented.
141125: Dynamic entries (from accepted local fits) check implemented. (Rejection of local fits may lead to the loss of degrees of freedom.) Printout of global parameter counters with new command printcounts.
141126: Weighted constraints implemented (with new command weightedcons).
150210: Solution by elimination for problems with linear equality constraints has been implemented (as default, new command withelimination) in addition to the Lagrange multiplier method (new command withmultipliers).
150218: Skipping empty constraints (without variable parameters). With new command checkinput detailed check of input data (binary files, constraints) is performed, but no solution will be determined. Some input statistics is available in the output file millepede.res.
150226: Iteration of entries cut with new command iterateentries. In the second iteration measurements with any parameters fixed by the previous entries cut are skipped. Useful if parameters of measurements have different number of entries.
150420: Skipping of empty constraints has to be enabled by new command skipemptycons.
150901: Preconditioning for MINRES with skyline matrix (avoiding rank deficits of band matrix) added (selected by second argument in bandwidth >0).
150925: Monitoring of residuals per local fit cycle is selected by monitorresiduals. The normalized residuals are grouped by the first global label and the median and the RMS (from the median of the absolute deviations) per group are written to millepede.mon.
170502: Monitoring of pulls per local fit cycle is selected by monitorpulls. The scaling of measurement errors is enabled by scaleerrors. Pede will abort now for constraints with a singular QL decomposition of the constraints matrix (solution by elemination). This problem is usually caused by empty constraints (see skipemptycons).
170831: More debug information for problems with reading Cfiles. Don't stop after read error for checkinput mode.
180525: Some fixes: Proper handling of special (debug) data blocks in binary files, proper exit code (3) for 'function not decreasing'.
180815: Some minor fixes, additional level of detail (appearance range of global parameters in binary files) for checkinput mode.
190319: Constraints are now sorted and split into disjoint blocks to speed up calculation of rank and QL decomposition by block matrix algebra. This works best if the label sets of the involved alignable objects are disjoint too.
190412: Cleanup of operations (open, close, rewind) on binary files. New command closeandreopen to enable closing and reopening of binary files to limit the number of concurrently open files. The modification dates of the files are monitored to ensure data integrity.
190430: Update of (approximate) string matching for keyword detection. Matching is now symmetric in pattern and text. Previously e.g. a binary file with the letters from 'Cfiles' in the name in that order was treated as that keyword and not as a binary file.
191004: Checking global parameters for disjoint blocks. In case of solution by inversion (optionally with constraints handled by elimination) switch to block diagonal storage mode.
200429: Modifications for compilation with PGI compiler (make -f Makefile_pgi).
200701: Implementation of parameter groups (sets of adjacent global parameters (labels) appearing in the binary files always together). Used to speed up construction of global matrix. Similarity operations are now aware of sparse (rectangular) matrices.
200716: The counting of the appearance of global parameters in the binary files can now be done on record (e.g. track) level instead of equation (e.g. measurement) level. This is enabled with the new command countrecords and makes the iteration of the first data loop (by iterateentries) obsolete.
201027: New solution method decomposition implemented.
201214: New command monitorprogress to monitor progress in operations on global and constraints matrices.
210301: New solution methods fullLAPACK and unpackedLAPACK (matrix factorization) based on LAPACK can be included optionally (at compile time, -DLAPACK64=..).
210728: Exploit decomposition of constraints matrix into disjoint blocks for all solution methods (e.g. QL decomposition, MINRES preconditioner).
211008: Fortran code modernized (EQUIVALENCE and ENTRY statements replaced) and checked (compiling with '-fcheck=all').
211022: Fortran code modernized further (assumed-size array arguments replaced).
211101: Migration from DESY svn to gitlab server (includes wiki).
211210: Further exploration of sparsity of constraints matrix (C). First the constraints are now split into disjoint groups for on optimized check of the rank of the product matrix (C*C^t). The groups are then combined into non overlapping blocks for an efficient QL decompsition in case of elimination of constraints. For solution by "unpackedLAPACK" the QL decomposition is now using the internal sparsity-aware code as default. To use LAPACK routines for this the new command withlapackelimination has to be used.
211222: Constraints groups included in checkinput. Documentation for Check input mode and Troubleshooting added.
220616: Cleanup, test programs to print LAPACK (library) configuration added to tools directory.
220817: Cleanup, (rare) problem with construction of parameter groups fixed (avoiding aborts with exit code 35).
221010: Fix (uninitialsed values) and cleanup for internal silicon strip tracker example.
221017: More code modernisation to comply the with fortran standard 2018 (gcc11 -std=f2018 -fall-intrinsics). Still some GNU fortran extensions are used: etime, fdate, getarg, getenv, iargc, stat, system, time
221122: Cleanup and documentation/exercises for example (internal test case -t=BRLF).
221212: Force check input mode (2) in case of accepted empty constraints (no variable parameters). No solution will be calculated.
230201: Fix global parameter errors for solution by diagonalization using elimination of constraints.
230321: Fortran/C interoperability uses now 'iso_c_binding' (fortran 2003) instead of 'cfortran.h'.
230322: Tool readMilleBinary.py now compatible with python3, updated CLI.
230502: Cleanup and fixes (constraint elimination with LAPACK using constraint groups, proper termination of file names for 'iso_c_binding')
230515: Check for redundancy constraints: Constraint groups defining linear transformation between two groups of equivalent global parameters. With the new command resolveredundancycons they can be resolved (to save resources and burden on numerics). Optionally add (brief) comments for global parameters to annotate the results file.
230516: New command checkparametergroups to check (the rank (linear independency of global derivatives) for) (global) parameter groups.
230617: Fix problem with monitoring of residuals. Calculate skyline fraction for sparse matrices.
230822: Fix problem for block diagonal global matrix (keeping single block).
231020: Define proper line search parameters for LAPACK too.
231218: New optional method sparsePARDISO using the Intel oneMKL PARDISO solver for sparse matrices.
240214: Fix severe problem with external measurements depending on multiple global parameters.
240227: Quick fix for possible integer overflow in summing up global Chi2 (ADDSUM). Needs careful revision.
240229: Summation of global Chi2 and NDF revised (no more 32bit variables, update per record).
240412: Counters scaling with the number of records are now long (64bit) integers.

Tools

The subdirectory tools contains some useful scripts:

readMilleBinary.py: Python script to read binary files and print records in text form.
compareResults.py: Python2 script to compare result files (millepede.res).
readPedeHists.C: ROOT script to read and convert the Millepede histogram file millepede.his.
lapack: Test programs to print LAPACK (library) configuration (MKL, OpenBLAS).

Details

Detailed information is available at:

Millepede II - Draft Manual

Major changes

List of options and commands

List of exit codes

Troubleshooting

Example

Contact

For information exchange the Millepede mailing list anace.nosp@m.ntre.nosp@m.-mill.nosp@m.eped.nosp@m.e2@de.nosp@m.sy.d.nosp@m.e should be used.

References

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) and hep-ex/0208021
Alignment Algorithms, V. Blobel, Proceedings of the LHC Detector Alignment Workshop, September 4 - 6 2006, CERN
Software alignment for Tracking Detectors, V. Blobel, NIM A, 566 (2006), pp. 5-13, doi:10.1016/j.nima.2006.05.157
A new fast track-fit algorithm based on broken lines, V. Blobel, NIM A, 566 (2006), pp. 14-17, doi:10.1016/j.nima.2006.05.156
Millepede 2009, V. Blobel, Contribution to the 3rd LHC Detector Alignment Workshop, June 15 - 16 2009, CERN
General Broken Lines as advanced track fitting method, C. Kleinwort, NIM A, 673 (2012), pp. 107-110, doi:10.1016/j.nima.2012.01.024
Volker Blobel und Erich Lohrmann, Statistische und numerische Methoden der Datenanalyse, Teubner Studienbücher, B.G. Teubner, Stuttgart, 1998. Online-Ausgabe.
Systems Optimization Laboratory, Stanford University;
C. C. Paige and M. A. Saunders (1975), Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12(4), pp. 617-629.
Systems Optimization Laboratory, Stanford University;
Sou-Cheng Choi, Christopher Paige, and Michael Saunders, MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM Journal of Scientific Computing 33:4, 1810-1836, 2011, doi:10.1137/100787921