\chapter{Reconstruction} %Youri Belikov the editor of this chapter. \label{CH:Reconstruction} \section{Organization of the reconstruction code} The ALICE reconstruction code is part of the \aliroot framework. Its modular design allows its code to be compiled into separate shared libraries and executed independently on the other parts of \aliroot. As an input, the reconstruction uses the digits, \ie ADC or TDC counts together with some additional information like module number, readout channel number, time bucket number, etc. The reconstruction can use both digits in a special \ROOT format, more convenient for development and debugging purposes, and digits in the form of raw data, as they are output from the real detector or can be generated from the simulated special-format digits above (see Fig.~\ref{CH:Reconstruction:frame}). The output of the reconstruction is the Event Summary Data (ESD) containing the reconstructed charged particle tracks (together with the particle identification information), decays with the V$^0$ (like $\Lambda\rightarrow$ p$\pi$), kink (like charged K $\rightarrow\mu\nu$) and cascade (like $\Xi\rightarrow\Lambda\pi\rightarrow$ p$\pi\pi$) topologies and some neutral particles reconstructed in the calorimeters. \begin{figure}[htb] \centering \includegraphics*[width=100mm]{chap5fig/rec.eps} %\includegraphics*[height=70mm]{chap5fig/rec.eps} \caption{Interaction of the reconstruction code with the other parts of \aliroot.} \label{CH:Reconstruction:frame} \end{figure} The main steering reconstruction class, {\tt AliReconstruction}, provides a simple user interface to the reconstruction. It allows users to configure the reconstruction procedure, include or exclude from the run a detector, and ensure the correct sequence of the reconstruction steps: \begin{itemize} \item reconstruction steps that are executed for each detector separately (typical example is the cluster finding); \item primary vertex reconstruction; \item track reconstruction and particle identification (PID); \item secondary vertex reconstruction (V$^0$, cascade and kink decay topologies). \end{itemize} The {\tt AliReconstruction} class is also responsible for the interaction with the \aliroot I/O sub-system and the main loop over the events to be reconstructed belongs to this class too. The interface from the steering class {\tt AliReconstruction} to the detector-specific reconstruction code is defined by the base class {\tt AliReconstructor}. For each detector there is a derived reconstructor class. The user can set options for each reconstructor in the form of a string parameter. Detector-specific reconstructor classes are responsible for creating the corresponding specific cluster-, track- and vertex-finder objects and for passing the corresponding pointers to the {\tt AliReconstruction}. This allows one to configure the actual reconstruction process using different versions of the reconstruction classes at the detector level. The detailed description of the reconstruction in all the ALICE detectors can be found in Ref.~\cite{CH5Ref:PPR2}. %in Chapter 5 of the Physics Performance Report Volume 2~\cite{CH5Ref:PPR2}. Here we shall only outline briefly the most challenging parts of it. \section{Track reconstruction in the central detectors} A charged particle going through the detectors leaves a number of discrete signals that measure the position of the points in space where it has passed. These space points are reconstructed by a detector-specific cluster-finding procedure. For each space point we also calculate the uncertainty of the space-point position estimation. All of the central tracker detectors (ITS, TPC, TRD) have their own detailed parametrization of the space-point position uncertainties, however, some of the parameters can be fixed only at the track finding step (see below). The space points together with the position uncertainties are then passed to the track reconstruction. If, in addition to the space point position, the detector is also able to measure the produced ionization, this information can be used for the particle identification. Offline track reconstruction in ALICE is based on the Kalman filter approach~\cite{CH5Ref:billoir}. The detector specific implementations of the track reconstruction algorithm use a set of common base classes, which makes it easy to pass tracks from one detector to another and test various parts of the reconstruction chain. For example, we can easily switch between different implementations of the clustering algorithm or the track seeding procedure. This also allows us to use smeared positions of the simulated hits instead of the ones reconstructed from the simulated detector response, which is very useful for testing purposes. In addition, each hit structure contains the information about the track that originated it. Although, this implies the storage of extra information, it was proved to be very useful for debugging the track reconstruction code. The event reconstruction starts with the determination of the position of the primary vertex. This can be done prior to track finding by a simple correlation of the space points reconstructed at the two pixel layers of the ITS. As was demonstrated in Ref.~\cite{CH5Ref:prim}, the precision of $\sim 5\ \mu$m along the beam direction and about~$25\ \mu$m in the transverse plane is routinely achieved for the high multiplicity events. The information about the primary vertex position and its position uncertainty is then used during the track finding (seeding and applying the vertex constraint) and for the secondary vertex reconstruction. The combined track finding in the central ALICE detectors consists of three passes that are described below (see also Fig.~\ref{CH5Fig:comb}). \begin{figure}[t] \centering %\includegraphics*[width=65mm,height=62mm]{chap5fig/BarelRec.eps} \includegraphics*[width=70mm,height=66mm]{chap5fig/BarelRec.eps} \caption{Schematic view of the three passes of the combined track finding (see the text).} \label{CH5Fig:comb} \end{figure} \paragraph{Initial inward reconstruction pass.} The overall track finding starts with the track seeding in the outermost pad rows of the TPC. Different combinations of the pad rows are used with and without a primary vertex constraint. Typically more than one pass is done, starting with a rough vertex constraint, imposing the primary vertex with a resolution of a few centimetres and then releasing the constraint. At first, we implemented the TPC track finding in a classical approach where cluster finding precedes the track finding. In addition, we also developed another approach where we defer the cluster finding at each pad row until all track candidates are propagated into its position. This way we know which of the clusters are susceptible to be overlapped and we may attempt cluster deconvolution at that specific place. In both approaches the track candidates are propagated and new clusters assigned to them using Kalman filtering. Then, for each track reconstructed in the TPC, we search for its prolongation in the ITS. In the case of high-multiplicity events this is done by investigating a whole tree of possible track prolongations. First, we impose a rather strict vertex constraint with a resolution of the order of 100~$\mu$m or better. If a prolongation is found, the track is refitted releasing the constraint. If the prolongation is not found we try another pass, without the vertex constraint, in order to reconstruct the tracks coming from the secondary vertices well separated from the main interaction point. We thus obtain the estimates of the track parameters and their covariance matrix in the vicinity of the interaction point. At this moment we can also tell which tracks are likely to be primary. This information is used in the subsequent reconstruction steps. \paragraph{Outward reconstruction pass and matching with the outer detectors.} From the innermost ITS layer we proceed with the Kalman filter in the outward direction. During this second propagation we remove from the track fit the space points with large $\chi^2$ contributions. In this way we obtain the track parameters and their covariance matrix at the outer TPC radius. We continue the Kalman filter into the TRD and then match the tracks toward the outer detectors: the TOF, HMPID, PHOS and EMCAL. When propagating the primary track candidates outward, we also calculate their track length and time of flight for several mass hypotheses in parallel. This information is needed for the PID in the TOF detector. \begin{figure}[htb] \centering \includegraphics*[width=110mm]{chap5fig/tpcits_efficiency.eps} \caption{Combined track reconstruction efficiency (closed symbols) and probability of obtaining a fake track (open symbols) as a function of transverse momentum for different track multiplicities.} \label{CH5Fig:eff} \end{figure} %\begin{figure}[htb] %\centering %\includegraphics*[width=110mm]{chap5fig/pt_res_2_100_4.eps} %\caption{Momentum resolution as a function of particle momentum for %high-momentum tracks and different detector configuration.} %\label{CH5Fig:ptres} %\end{figure} \paragraph{Final reconstruction pass.} After the matching with the outer detectors, all the available PID information is assigned to the tracks. However now the track momenta are estimated far away from the primary vertex. The task of the final track reconstruction pass is to refit the primary tracks back to the primary vertex or, in the case of the secondary tracks, as close to the vertex as possible. This is done again with the Kalman filter using in all the detectors the clusters already associated at the previous reconstruction passes. During this pass we also reconstruct the secondary vertices (V$^0$s, cascade decays and kinks). The whole procedure is completed with the generation of the ESD. A typical ESD for a central \mbox{Pb--Pb} event contains about $10^4$ reconstructed tracks, a few hundred V$^0$ and kink candidates, and a few tens of cascade particle candidates. \paragraph{Performance of the track reconstruction.} Figure~\ref{CH5Fig:eff} shows the efficiency of the combined track reconstruction as a function of particle momentum for events with different multiplicities. The track reconstruction efficiency is defined as a ratio of the number of reconstructed `good' tracks to the number of `good' generated tracks (for the definition of the `good', in other words `reconstructable', tracks see~\cite{CH5Ref:tpc}). Some of the reconstructed tracks can be associated with a certain number of clusters which do not belong to those tracks. The probability of obtaining such tracks (`fake' tracks) is also shown in this picture. One can see that even in the case of events with the highest expected multiplicity, the track-finding efficiency is always above 85\% and the number of the `fake' tracks never exceeds a few per cent. The momentum resolution obtained with different detector configurations and different versions of the reconstruction in the TRD is shown in Fig.~\ref{CH5Fig:ptres}. In all the cases the resolution at 100~GeV/$c$ is better than 5\%. \begin{figure}[htb] \centering \includegraphics*[width=110mm]{chap5fig/pt_res_2_100_4.eps} \caption{Momentum resolution as a function of particle momentum for high-momentum tracks and different detector configurations.} \label{CH5Fig:ptres} \end{figure} \section{Track reconstruction in the forward muon spectrometer} Since the muon spectrometer geometry is quite different from that of the central detectors (notably, the large distance (up to 2.5~m) between consecutive measurements), it was not obvious from the beginning that the Kalman filter would demonstrate the best performance possible as compared with other methods. That is why another algorithm was developed originally which further served as a reference point for Kalman filter studies. %\begin{figure}[htb] %\centering %\includegraphics*[width=110mm]{chap5fig/mass-2-new.eps} %\caption{Reconstructed dimuon invariant mass in the region of the %$\Upsilon$ mass.} %\label{CH5Fig:muon} %\end{figure} This original method was motivated by the Kalman filter strategy, i.e.\ implements a simultaneous track finding and fitting approach as follows. Track candidates start from segments (vectors) found in the last two tracking stations, where a segment is built from a pair of points from two chamber planes of the same tracking station. Then each track is extrapolated to the first station, and segments or single hits found in the other stations are added sequentially. For each added station, the track candidate is refitted and the hits, giving the best fit quality, are kept. In order to increase the track-finding efficiency the procedure looks for track continuation in the first two stations in direct and reverse order. A track is validated if the algorithm finds at least 3 hits (out of 4 possible) in the detector planes behind the dipole magnet, at least 1 hit (out of 2) in the station located inside the magnet and 3 hits (out of 4) in the chambers before the magnet. For a Kalman track reconstruction, tracks are initiated for all track segments found in the last two detector stations as for the previous method. The tracks are parametrized as $(y, x, \alpha, \beta, q/p)$, where $y$ is a coordinate in the bending plane, $x$ is a non-bending coordinate, $\alpha$ is a track angle in the bending plane with respect to the beam line, $\beta$ is an angle between the track and the bending plane, $q$ and $p$ are the track charge and momentum, respectively. A track starting from a seed is followed to the first station or until it is lost (if no hits in a station are found for this track) according to the following procedure. It propagates the track from the current $z$-position to a hit with the nearest $z$-coordinate. Then for given $z$ it looks for the hits within a certain window $w$ around the transverse track position. After this there are two possibilities. The first one is to calculate the $\chi^2$-contribution of each hit and consider the hit with the lowest contribution as belonging to the track. The second way is to use the so-called track branching and pick up all the hits inside the acceptance window. Efficiency and mass resolution tests have shown that the second way gives a better result. After propagation to the chamber 1 all tracks are sorted according to their quality $Q$, defined as \begin{equation} Q = N_{\rm hits} + \frac{\chi^2_{\rm max}-\chi^2}{\chi^2_{\rm max}+1}, \nonumber \end{equation} where $\chi^2_{\rm max}$ is the maximum acceptable $\chi^2$ of tracks and $N_{\rm hits}$ is the number of assigned hits. Then duplicated tracks are removed, where duplicated means having half or more of their hits shared with another track with a higher quality. Both of the track-finding approaches take advantage of an advanced unfolding of overlapped clusters~\cite{CH5Ref:hit}. The method exploits a so-called Maximum Likelihood - Expectation Maximization (MLEM or EM) deconvolution technique~\cite{CH5Ref:mlem} (also known as Lucy-Richardson method or Bayesian unfolding). The essence of the method is that it iteratively solves the inverse problem of a distribution deconvolution. It is widely used in nuclear medicine for tomographic image reconstruction, in astronomy, and was also successfully tried for hit finding in silicon drift detectors. Effectively, this method improves the detector segmentation offering better conditions for making a decision about complex cluster splitting. \begin{figure}[htb] \centering \includegraphics*[width=110mm]{chap5fig/mass-2-new.eps} \caption{Reconstructed dimuon invariant mass in the region of the $\Upsilon$ mass.} \vspace{5mm} \label{CH5Fig:muon} \end{figure} Under typical conditions, the track-finding efficiency of both of the methods is higher than 90\%, with the Kalman filter approach being faster and giving a better resolution. As an example of the results of the track reconstruction in the forward muon spectrometer, Fig.~\ref{CH5Fig:muon} shows the reconstructed $\Upsilon$ invariant mass. \section{Charged particle identification} Particle identification over a large momentum range and for many particle species is often one of the main requirements of high-energy physics experiments. The \mbox{ALICE} experiment is able to identify particles with momenta from 0.1~GeV/$c$ to, in some cases, above 10 GeV/$c$. This can be achieved by combining several detecting systems that are efficient in narrower and complementary momentum sub-ranges. This combining is done following a Bayesian approach. The method is similar to the one described in Ref.~\cite{CH5Ref:fis} and satisfies the following requirements: \begin{itemize} % \item It is automatic. \item It can combine the PID signals of different nature (\eg d$E$/d$x$ and time-of-flight measurements). \item When several detectors contribute to the PID, the procedure profits from this situation by providing an improved PID. \item When only some of the detectors identify a particle, the signals from the other detectors do not affect the combined PID. \item It takes into account the fact that the PID results depend on a particular track and event selection used in the analysis. \end{itemize} \begin{figure}[htb] \centering \includegraphics*[width=78mm]{chap5fig/ITSpid.eps} \includegraphics*[width=78mm]{chap5fig/TPCpid.eps} \includegraphics*[width=78mm]{chap5fig/TOFpid.eps} \includegraphics*[width=78mm]{chap5fig/ALLpid.eps} \caption{Single-detector efficiencies (solid line) and contaminations (points with error bars) of the charged kaon identification with the ITS, TPC and TOF stand-alone and the efficiency and contamination with all the detectors combined together.} \label{CH5Fig:PID} \end{figure} The PID procedure consists of three parts: \begin{itemize} \item The conditional probability density functions $r(s|i)$ to observe a PID response $s$ from a particle of type $i$ (the single-detector PID response functions) are obtained for all the detectors that provide the PID information. This is done by the calibration software using the Event Summary Data (ESD) for a subset of events as an input. \item For each reconstructed track, the global PID response $R(\bar{s}|i)$, which is a combination of the single detector response functions $r(s|i)$, is calculated taking into account possible effects of mis-measured PID signals. The results are written to the ESD and, later, are used in the physics analysis of the data. This is part of the reconstruction software. \item Finally, during a physics analysis, after the corresponding event and track selection is done, the {\it a priori} probabilities $C_i$ for a track to be a particle of a certain type $i$ within that selected track subset are estimated and the PID weights $W(i|\bar{s})$ are calculated by means of Bayes's formula: \begin{equation}\label{eq:bayes1} W(i|\bar{s})={R(\bar{s}|i) C_i \over \sum_{k=e, \mu, \pi, ...}{R(\bar{s}|k) C_k}} ,\ \ \ i=e, \mu, \pi, ... \end{equation} This part of the PID procedure belongs to the analysis software (see Chapter 5 of the ALICE Physics Performance Report Volume 2~\cite{CH5Ref:PPR2} for the details). \end{itemize} The performance of identifying charged kaons in central HIJING \mbox{Pb--Pb} $\sqrt{s_{NN}}=5.5$ TeV events using the ITS, TPC and the TOF as stand-alone detectors and the result for the combined PID are shown in Fig.~\ref{CH5Fig:PID}. A track was considered as a charged kaon track, if the corresponding PID weight was the maximal. The PID efficiency is defined as the ratio of the number of correctly identified particles to the true number of particles of that type entering the PID procedure, and the contamination is the ratio of the number of mis-identified particles to the sum of correctly identified and mis-identified particles. As can be seen in this figure, the efficiency and the contamination of the combined PID are significantly better, and less dependent on the momentum, than in the case of a single detector particle identification. The efficiency of the combined result is always higher than (or equal to) in the case of any of the detectors working stand-alone and the combined PID contamination is always lower than (or equal to) the contaminations obtained with the single detector PID. The approach can easily adopt the PID information provided by the TRD. This improves the PID quality for all the particle types (by using the d$E$/d$x$ measurements) and, in particular, for the electrons (by using the additional transition radiation signal)~\cite{CH5Ref:trd}. %The moment region over which the particles are identified is additionally %extended with the help of the HMPID detector. %The combined PID software for this detector is currently under development. \begin{figure}[htb] \centering \includegraphics*[width=120mm]{chap5fig/rich.eps} \caption{The correlation between the Cherenkov angle $\theta_c$ measured by HMPID and $\beta$ measured by TOF for different particle species as a function of the particle momentum.} \label{CH5Fig:rich} \end{figure} The identification of high momentum charged hadrons in the central rapidity region will be performed by the HMPID system, which consists of an array of seven RICH detectors. A combined identification of pions, kaons and protons between HMPID and TOF will be performed in momentum intervals partially overlapped, where a good PID for both the detectors could be achieved. The combined information from these detectors will improve the identification efficiency and will decrease significantly the contamination. The correlation between the reconstructed Cherenkov angle $\theta_c$ (measured by HMPID) and the $\beta$ (measured by TOF) of pions, kaons and protons as a function of the momentum has been studied in simulated HIJING \mbox{Pb--Pb} central events. The results are shown in Fig.~\ref{CH5Fig:rich}. The software to obtain the PID combined over HMPID and TOF is under development. \section{Photon and neutral meson reconstruction in the PHOS} Photons in ALICE are detected by the PHOton Spectrometer, PHOS~\cite{CH5Ref:phos}, consisting of an electromagnetic calorimeter to measure 4-momenta of photons and a charged-particle veto detector (CPV) to discriminate neutral and charged particles. %The electromagnetic calorimeter %consists of a cellular structure of scintillating crystals of lead %tungstate. The reconstruction algorithms and particle identification %in PHOS is described in details in the Chapter 5 of the ALICE %PPR~\cite{CH5Ref:PPR2}. All the particles hitting the PHOS interact with the calorimeter medium producing showers, and deposit energy in its cells. %The measured amplitude of the signal cells is %proportional to the deposited energy in the cells. The cells with signals are grouped into clusters that allow one to evaluate the total energy deposited by the particles in the calorimeter and the coordinate of the particle impacts on the surface of the detector. A special unfolding procedure is applied to split the clusters produced by particles with overlapping showers. %The radiation length of the electromagnetic calorimeter %provides total energy absorption for photons and electrons which %allows to measure precisely their 4-momenta. The energy resolution for %photons achieved in PHOS is $\sigma_E/E = 0.022/E \oplus %0.028/\sqrt{E} \oplus 0.013$, and the position resolution for normally %incident photons is $\sigma_x = 2.6~\mbox{mm}/\sqrt{E} \oplus %0.3~\mbox{mm}$, where energy $E$ is measured in GeV. The CPV detector %is sensitive to all charged particles and measures their 2-dimensional %coordinates on a surface at 12~cm above the calorimeter with the %accuracy better than 0.2~mm. %\subsection{Particle identification in PHOS} The particle identification in PHOS is based on three criteria~\cite{CH5Ref:PPR2}: time-of-flight measurement, shape of the showers produced by different particles in the calorimeter, and matching of the reconstructed point in the calorimeter and the reconstructed point in the CPV detector. The time of flight between the beam interaction time and the detection in PHOS is measured by the front-end electronics and allow the suppression of slow particles, especially low-energy ($E<2$~GeV) nucleons. The shower shape produced by photons and electrons is different from the showers produced by hadrons. This difference is used to discriminate particles interacting with the calorimeter electromagnetically and hadronically. Matching of the charged particles with the calorimeter reconstructed point is provided by the CPV detector and allows the selection of neutral particles. %Being %applied together, these three identification critaria provide high %identification capability for photons and electrons. The average %number of all reconstructed particles in PHOS per one the most central %Pb-Pb collision is about 100, and half of them are identified as %photons. %\subsection{Direct photon and neutral meson reconstruction} The direct photons are measured as an excess of the photon spectrum over the decay photons. To measure the decay photon spectrum, one reconstructs the spectra of neutral mesons decaying into photons ($\pi^0$, $\eta$, $\omega$, etc). These spectra at low $p_{\rm t}$ are measured statistically via invariant-mass spectra of all photon combinations. In the high-multiplicity environment of heavy-ion collisions, the combinatorial background for the invariant-mass spectra is very high. As a demonstration, the spectrum of two-photon invariant mass at $1