Millepede II is the successor of Millepede, a package for linear least squares fits with a large number of parameters. Both have been developed as experiment independent programs by Prof. V. Blobel. Documentation and source code of Millepede and of the first version of Millepede II are available on his web page (or mirror). Meanwhile, the Statistics Tools group of the Analysis Centre took over the maintenance of Millepede II.
The first Analysis Centre release, version V02-00-01, contains V. Blobel's 2009 development and small changes/fixes coming from CMS experience by G. Flucke. Further development, mainly by C. Kleinwort for usage in CMS, adds
Using these features allows CMS silicon tracker alignment to determine 200 000 parameters in one go fitting more than 20 million tracks, including 3.6 million cosmic ray tracks and about 375 thousand muon pairs from Z decays reparametrised as one fit object with a vertex constraint and adding a virtual Z mass measurement (cf. CMS-CR-2011-323). The computing requirements on an Intel™ Xeon™ L5520 with 2.27 GHz using eight threads are 44.5 h CPU (but only 10 h wall clock time) and less than 32 GB of RAM.
The project has been migrated to GitLab at DESY (code and wiki).
The source code of Millepede II is provided by DESY under the terms of the LGPLv2 license and is maintained in a publicly accessible subversion repository at DESY that can be browsed via viewvc or WebSVN.
The recommended version is publicly available via the subversion command line:
svn checkout http://svnsrv.desy.de/public/MillepedeII/tags/V04-10-01 MillepedeII
For development, please check out the trunk:
svn checkout https://svnsrv.desy.de/desy/MillepedeII/trunk MillepedeII
You could replace /desy/ by /svn/ or /basic/ for other authenticiation methods, see subversion server access info. To be allowed to commit, please contact the mailing list, mentioned below.
In addition tarballs can be found here.
The delivered Makefile foresees the compilation of a single pede executable with dynamic allocation of memory. Simple 'cd MillepedeII; make', compiles the executable. This requires gcc version 4.4 or higher. For larger problems (>8GB of memory) a 64bit system is necessary.
The delivered Makefile foresees the compilation of pede executables with different amount of memory. Simple 'cd MillepedeII; make', compiles three executables: pede (400 MB memory), pede_1GB and pede_2GB (memory as the name indicates). If your problem requires more space due to a high number of parameters or a dense matrix, you need a 64-bit system and probably a special compiler flag, see the comments in the Makefile. The maximum memory possible is with 32 bit integers for internal (FORTRAN) memory management 2147483647 = (231 - 1) words, i.e. about 8.5 GB. With version V03-01-00 64 bit integers are available (FORTRAN95, gfortran) to overcome this limit.
The Makefile of the recent version is written for gcc 4.1.2 (the reference compiler is: gcc version 4.1.2 20080704 (Red Hat 4.1.2-50) ), but it works for later gcc relases until 4.4.X. See comments in the Makefile to make it work for gcc version 3.X.Y (64 bit integers not recommended) or gcc 4.5.X and 4.6.X. Please contact the mailing list about necessary fixes you know about to use other compilers.
The gcc 4.4.0 compiler is not recommended. When starting from perfect alignment, we noticed that it can happen that pede stops without finding a non-trivial minimum ("Function not decreasing..."). This is not understood, but since gcc 4.1.2 and gcc 4.3.4 behave like expected, i.e. finding small corrections, we guess that it is a gcc 4.4.0 problem. Update: Same seen also with gcc 4.5.1! Needs to be investigated...
Starting with gcc 4.4 the MINRES pre-conditioner for bandwidth zero (PRECON) is not compiled correctly. This problem is avoided with version V03-04-01 by rearranging some lines in the source code.
Since version V04-00-00 documentation with doxygen is available in html format.
The project has been migrated to GitLab at DESY (code and wiki).
Fortran code modernized further (assumed-size array arguments replaced). Additional cases of out of range read access fixed.
The code quality has been improved. Compilation with '-fcheck=all’ has been used to check for out of index range array access (few cases for read access found and fixed) and ancient Fortran statements have been replaced. For one user an EQUIVALENCE statement in the internal histogramming produced (with gcc10) memory corruption with NANs leading to an indefinite loop.
Fixed uninitialized values in QL decomposition of constraints matrix (introduced in V04-09-04).
Exploit sparsity and decomposition of constraints matrix into disjoint blocks for all solution methods (e.g. QL decomposition, MINRES preconditioner).
Memory allocation for internal histograms is now dynamic in terms of number of binary files.
The warning messages for severe warnings (exit code 2) have been improved.
All indices for constraint matrices have been upgraded to 64 bit. Previously a segmentation fault happened for (number of parameters) * (number of constraints) >= 2^31.
Optional usage of external linear algebra libraries to speed up solution. Implemented has been LAPACK and tested with the Intel MKL and the OpenBLAS library.
Two new solution methods based on matrix factorisation are available optionally: fullLAPACK
and unpackedLAPACK
. They differ in the LAPACK storage mode (packed vs unpacked).
New command monitorprogress
to monitor progress in operations on global and constraints matrices with additional printout into the log file.
Fixing potential integer overflows for elimination of constraints. This happens for all solution methods except MINRES if the square of the number of (variable global) parameters is larger than 2^31.
New solution method (Cholesky) decomposition
added. It's faster than inversion but does not calculates parameter errors.
Bug fix (integer overflow) and little speedup (~15%) for solution of large problems by inversion.
The solution by inversion with Lagrange multipliers has been fixed. (It was broken since V04-06-00.)
More robust sorting of constraints for splitting into disjoint blocks.
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.
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.
Solution with method sparseMINRES
got considerably faster.
Modifications for compilation with PGI compiler (make -f Makefile_pgi
).
Checking global parameters for disjoint blocks now. In case of solution by inversion (optionally with constraints handled by elimination) switch to block diagonal storage mode (to save memory and cpu time).
Method sparseMINRES
fine again.
Improved stability. The line search is now skipped in case the current solution is numerically too close to the minimum. Method sparseMINRES
broken due to bad back port from development version.
Two (very old) cases of access to arrays outside of the defined bounds (reported by gcc9) have been fixed.
Fix for modified text parser (concerning leading blanks in lines with only numbers).
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.
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.
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.
Some minor fixes, additional level of detail (appearance range of global parameters in binary files) for checkinput mode.
Fixes for special data blocks and not decreasing function value.
More debug output in case of problems reading the binary Cfiles.
Fix for downweighting correction (Cauchy) of global chi2.
Fix for abort on singular QL decomposition of constraints matrix.
Monitoring of pulls (monitorpulls
) and scaling of measurement errors (scaleerrors
) from binary files added. Abort now in case of singular QL decomposition of constraints matrix (solution by elimination).
Bug fix for monitoring of residuals.
Contains few fixes, mainly improved response to numerical problem leading before to "Function not decreasing".
The monitoring of the residuals per local fit cycle has been implemented and 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 the new text file millepede.mon
.
Contains fixes and improvements for MINRES preconditioning:
Contains some new features:
withelimination
) in addition to the Lagrange multiplier method (new command withmultipliers
).skipemptycons
.checkinput
detailed checks of input data (binary files, constraints) are performed, but no solution will be determined. Some input statistics is available in the output file millepede.res
.iterateentries
. In the second iteration measurements with any parameters fixed by the previous entries cut are skipped. Useful if for some measurements different parameters have different number of entries.
Contains some new features:
weightedcons
.
Contains some new features:
Printout of global parameter counts from binary files added to result file with new option printcounts
.
Aborting in case of (C) read errors.
Storage of values read from text files as doubles implemented.
Integer overflow in auto detection of bordered band matrices for local fits with huge number of parameters fixed.
The reading of records from C binary files containing doubles (indicated by negative record length) instead of floats has been implemented. The complete local fit is now in double precision.
Integer overflow in auto detection of bordered band matrices for local fits with huge number of parameters fixed.
Fixed V04-01-02.
Has bug, crashing with gcc-4.8.
Contains some minor fixes, e.g:
tools/readMilleBinary.py
) to print binary files accepts now command line arguments (file name, number of records).
The exit code and message of the pede executable are written to the file millepede.end
:
Solution method MINRES-QLP added. This advanced MINRES version is selected by 'method sparseMINRES-QLP ..
' or 'method fullMINRES-QLP ..
'.
Fixes for integrity check of binary files (program abort) and reading of MINRES tolerance parameter (mrestol
set to zero).
Added checks of integrity of binary files. The integers are checked for the consistency of labels and markers (zeros) and the floats for NaNs (not a number).
Allow parallel make and other minor changes to Makefile, e.g.remove option for LARGE integers to be INTEGER*4 to allow compilation on 32-bit systems (but medium size problem now require a bit more memory).
The line search to optimize the solution is now configurable. The new option linesearch
allows to select the iterations (solutions) with line search: >2: all, =2: all with (next) Chi2 cut scaling factor =1., =1: last, <1: none. The default value is '2', the previous behaviour corresponds to '3'.
Minor fixes. Option 'maxrecord
' working again with OpenMP.
First "fortran90" version. The source code has been transformed from fixed form (punch card image) Fortran77 to free form fortran90. Major changes:
Bug fixes:
memorydebug
' (1: just printing, >1: more debug).
Minor bug fix to tools/readPedeHists.C to read pede histogram output.
Bug fixes: (global matrix) update cache buffer overrun from rejected records; integer overflow for final rejection ratio.
Compilation problem for gcc version 4.4/4.5 avoided for MINRES pre-conditioner. New features:
errlabels
') too.globalcorr
'.
New features:
Cleanup of printout and new features:
errlabels <lab1> .. <labn>
' to define up to 100 global parameters for which errors are calculated.threads <nproc> <nread>
' the number of threads for processing (nproc) and reading binary files (nread) in parallel can be specified.
Methods inversion and diagonalization working again!
Methods inversion and diagonalization broken!
pairentries
'.maxrecord <record>
' to set record limit for input from binary files.matmoni <record>
' to monitor construction of sparse global matrix. Every <record> records the number of off-diagonal elements, the compression ratio and the memory consumption is printed.
Methods inversion and diagonalization broken!
compress
' the sparsity information is compressed and off-diagonal elements with single entries are stored in single precision (lossless as input from binary file is single precision only). With 'pairentries <ncut> <nhist> <nsingle>
' off-diagonals with up to <nsingle> entries are stored in single precision (unintended feature: for nsingle=2n-1 and nhist<=nsingle all off-diagonals are in single precision).method sparseMINRES
'. Most time is spent in AVPROD (multiplication of global matrix with vector). This has been parallelized with OpenMP™. The number of threads are specified with 'threads <nthread>
'.mrestol <rtol>
'.
Large Integers are used for internal (FORTRAN) memory management. The Makefile allows to select 32 bit (LARGE_SIZE=4) or 64 bit (LARGE_SIZE=8) integers.
pairentries <ncut> <nhist>
' implemented. Rare global parameter pairs (off-diagonal elements of global matrix) with less than <ncut> entries are neglected. Optional <nhist> defines upper bound for histogramming.chisqcut f1 f2
' with f1<1.0 will disable Chi2 cut (including Huge) in FIRST iterationsubito
' option reimplemented (lost since V02-00-00)entries n
' checks for n>0 (n=max(1,n))debug
' some more statistics for fixed parameters is calculated (fraction of equations, records with fixed parameters)
Recent development has been presented at the 3rd LHC Detector Alignment Workshop in June 2009 by Prof. Blobel. The main new features/changes are:
sparseMINRES
', 'fullMINRES
', 'inversion
' and 'diagonalisation
', others have been removed.bandwidth 0
' specified),matiter <number>
': Force re-calculation of the matrix in the first <number> iterations - slower, but more robust in case of large number of rejects due to too many outliers.presigma <number>
': Assign pre-sigma <number> to all labels where no explicit presigma is set.regularisation <number>
': Regularisation with τ = <number>, i.e. add τ ∙ ‖x‖ to the minimised function where x is the vector of alignment parameters, weighted with the inverse of their individual presigma; this should reduce the influence of weak modes, but needs careful studies.regularisation <number1> <number2>
': Same as having both 'regularisation <number1>
' and 'presigma <number2>
'.hugecut <number>
': to determine huge outlier rejection cut that is always active, irrespective of chisqcut settings, default stays at 50, minimum value is 1.0..txt
'.
The manual still needs to be updated.
For the input to pede the resources (memory, handles for C binary files, ..) are allocated dynamically and may be limited by the system. The are no explicit limits on the number of global parameters or number of (C) binary files.
For the internal monitoring some arrays still have fixed size:
JFLC(5,IG) = 200
in 'mphistab.F', take care that NARR = NUMGXY * "desiredValue"
- if more points requested, points are averaged).
For the steering text files the maximal length of a line is 1024 characters. This limits the length of file names too.
Since pede is Fortran77, several array lengths have a fixed size, e.g.
PARAMETER (MFILES=500
) in 'mpinds.inc'), maximum number of C-binaries is 490 (#define MAXNUMFILES 490
in 'readc.c')CHARACTER*500 TFD(MFILES)
in 'mpinds.inc')JFLC(5,IG) = 200
in 'mphistab.F', take care that NARR = NUMGXY * "desiredValue"
- if more points requested, points are averaged).
The given values refer to version 90 of the trunk (i.e. tag V03-04-04) .
Following user requests will be considered for future releases. Please contact the mailing list (see below) for bug reports or user requests.
Your are welcome to join the mailing list that will be used for announcements, but should also serve for user questions and discussions. You are also allowed to post questions without subscribing, though subscription is preferred.
This list is probably incomplete - you are very welcome to add yourself!
CMS has been the main user driving the developments during LHC run 1.