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.
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-11-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.
Tools
The subdirectory tools
contains some useful scripts:
readMilleBinary.py:
Python script to read binary files and print records in text form.
readPedeHists.C:
ROOT script to read and convert the Millepede histogram file millepede.his
.
Details
Detailed information is available at:
Millepede II - Draft Manual
Major changes
List of options and commands
List of exit codes
Troubleshooting
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] (https://indico.cern.ch/conferenceOtherViews.py?view=standard&confId=50502) 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