diff options
Diffstat (limited to 'report/report.tex')
| -rw-r--r-- | report/report.tex | 42 |
1 files changed, 34 insertions, 8 deletions
diff --git a/report/report.tex b/report/report.tex index 00a8730..3878ec0 100644 --- a/report/report.tex +++ b/report/report.tex @@ -6,7 +6,7 @@ \usepackage{xcolor} \usepackage{graphicx} -\graphicspath{{./figures/} {./figures/tracy-widom-approx/}, {./figures/results/}} +\graphicspath{{./figures/} {./figures/tracy-widom-approx/}, {./figures/results/} {./figures/wall-times/}} \usepackage{amsmath} \usepackage{booktabs} \usepackage{longtable} @@ -162,7 +162,7 @@ The manager process is relatively straightforward and focuses more on the `book \label{alg:manager} \end{algorithm} -Note that the actions labelled with involving MPI communication that is blocking, i.e., the worker/manager will wait to receive a broadcast before continuing at all. +Note that the actions labelled with involving MPI communication are blocking, i.e., the worker/manager will wait to receive a broadcast before continuing at all. \subsection{The Calculation (Worker) Process} The worker process involves calculating the eigenvalues and is more complicated than the manager process. Various sub-processes are included in different algorithms, namely for building the matrix, computing the eigenvalue, and applying the power method. The overview of the whole process is outlined in Algorithm \ref{alg:worker}: @@ -173,7 +173,7 @@ The worker process involves calculating the eigenvalues and is more complicated \State size $\gets$ \texttt{MPI Receive}: matrix size \State Initialize matrix space in memory \While{Worker not Finished} - \State seed $\gets$ \texttt{MPI Receieve}: new matrix seed + \State seed $\gets$ \texttt{MPI Receive}: new matrix seed \State Call \texttt{open\_prng\_seed}(seed) \State matrix $\gets$ \texttt{build\_random\_matrix}(size) \State eig $\gets$ \texttt{calculate\_eigenvalue}(matrix) @@ -255,7 +255,11 @@ So far the structure has involved a minimal amount of math. This is only because \label{alg:power-iteration} \end{algorithm} -These algorithms compose the entirety of the program for reconstructing the Tracy-Widom distributions discussed earlier. +These algorithms compose the entirety of the program for reconstructing the Tracy-Widom distributions discussed earlier. It is worth noting that the expected complexity is a function of the required calculation complexity $n$, the number of MPI ranks used $m$, and the sample size $l$. Assuming a total FLOPs count of $\sim\mathcal{O}(n^3)$ in a worst-case scenario for Schur decomposition, repeated $l$ times, in reality each rank will only have to contribute 1-$m$th of the work. Note that while the QR algorithm is not done in parallel, repeating in $l$ times is embarrassingly parallel. So the total time complexity should be roughly: +\begin{equation} + \sim\mathcal{O}\left(\frac{n^3\, l}{m}\right) +\end{equation} +which will be tested in the next section. \section{Results} Before the eigenvalues can be directly compared to a Tracy-Widom they must be scaled to match the existing distribution. It is possible to perform the scaling empirically, but a closed-form solution is available that makes things easier \cite{konig2005}: @@ -265,7 +269,7 @@ Before the eigenvalues can be directly compared to a Tracy-Widom they must be sc This specific transform is derived from the Wigner semicircular distribution mentioned earlier in section 2. Although it describes the global distribution, taking the extrema yields a bound for the maximum eigenvalue. \subsection{Tracy-Widom Convergence} -Following some software issues related to the OneAPI suite, the author was unable to produce enough samples in time to complete the report. However, a moment is appropriate to thank all of the teammates for being kind enough to share their data for analysis in this report. The following numbers are from Joe's runs but all of the analysis was done individually. Samples here are presented with respect to their matrix dimension $N$, number of samples $L$, skewness $S$ and excess kurtosis $K$. Taking, for example, different sample sizes for $N=1750,500$ yields a half-dozen examples of a clear trend emerging where the histograms tend towards a normal-\emph{ish} shape, shown in Figure \ref{fig:randoms}: +Following some software issues related to the OneAPI suite, the author was unable to produce enough samples in time to complete this report. However, a moment is appropriate to thank all of the teammates for being kind enough to share their data for analysis in this report. The following numbers are from Joe's runs but the analysis was done individually. Samples here are presented with respect to their matrix dimension $N$, number of samples $L$, skewness $S$ and excess kurtosis $K$. Taking, for example, different sample sizes for $N=1750,500$ yields a half-dozen examples of a clear trend emerging where the histograms tend towards a normal-\emph{ish} shape, shown in Figure \ref{fig:randoms}: \begin{figure}[H] \centering @@ -283,6 +287,7 @@ Despite the visuals, however, the metrics tell a bleaker story. Recall that the \caption{Reconstructed distributions from the maximum number of samples $L_{max}$ for each size $N$. Table \ref{tbl:results} provides more information on the behaviour of skewness and excess kurtosis for the high-sample runs. Qualitatively, under filling seems prevalent at larger $N$ and a strong $-x$ tail is visible.} \label{fig:big-ones} \end{figure} +The parameters calculated for the distributions are presented in Table \ref{tbl:results} for convenience: \begin{table}[H] \centering @@ -302,21 +307,42 @@ Despite the visuals, however, the metrics tell a bleaker story. Recall that the \label{tbl:results} \end{table} +Despite the significant increase in sample size ($\sim10\times$ at a minimum), the skewness and excess kurtosis do not converge to their expected values. Rather, the skewness diverges from the expected value of 0.2935, and the excess kurtosis has a minimum error of at least 200\% relative to the expected 0.1292 described earlier. These trends are shown below in Figure \ref{fig:errors}: \begin{figure}[H] \centering \input{./figures/results/parameters.tex} - \caption{Reconstructed distributions from the maximum number of samples $L_{max}$ for each size $N$. Table \ref{tbl:results} provides more information on the behaviour of skewness and excess kurtosis for the high-sample runs. Qualitatively, under filling seems prevalent at larger $N$ and a strong $-x$ tail is visible.} + \caption{Behaviour of the two parameters skewness $S$ and excess kurtosis $K$ as function of matrix size $N$ for a maximal number of samples $L$. Observed responses are shown in solid lines, with the expected values being horizontal dotted lines and the percent-error represented with dashed lines. Neither of the trends observed in the skewness or expected kurtosis are consistent with theory, and their behaviours cannot confirm the existence of a Tracy-Widom distribution from the calculations.} \label{fig:errors} \end{figure} +The tendency of the skewness to diverge from zero as the matrix size increases does point to a non-Gaussian distribution being observed, but it cannot be concluded that it is a Tracy-Widom. + \subsection{Wall Times} +Lastly, the wall time of running the simulations was investigated. These results were more aligned with the expected values of complexity. Two different perspectives are considered: the variation of sample size with a constant matrix size, and the vice-versa case. The results for the constant sample sizes is discussed first as it should correspond to the complexity mentioned in Section 4. Figure \ref{fig:N_walltimes} shows a complexity tending to $\mathcal{O}(n^3)$ (with slight variations over the matrix size domain) for all sample sizes: +\begin{figure}[H] + \centering + \input{./figures/wall-times/N_walltimes.tex} + \caption{Wall times for different sample sizes $L$ as a function of the matrix size $N$. All runs were conducted using 128 MPI ranks for this figure. Wall times show a roughly $\mathcal{O}(n^3)$ scaling consistent between all sample sizes tested, although there is a magnitude difference between the fastest ($L=128$) and slowest ($L=4096$) runs.} + \label{fig:N_walltimes} +\end{figure} + +The vice-versa case shows a different story, with a complexity closer to $\mathcal{O}(n)$. This makes intuitive sense, as MPI ranks can calculate different matrices of a common sample in parallel, explaining the rather weak coupling. Compare this to increasing the matrix size itself, which is solved in serial by one rank at time, making the scaling appear much more sensitive to changes in the independent variable. The trend is visualized below in Figure \ref{fig:walltimes}: + +\begin{figure}[H] + \centering + \input{./figures/wall-times/walltimes.tex} + \caption{Wall times for different matrix sizes $N$ as a function of the number of sampled eigenvalues $L$. All runs were conducted using 128 MPI ranks for this figure. Wall times show a roughly $\mathcal{O}(n)$ scaling consistent between all matrix sizes tested, although there was a $\sim2$ magnitude difference between the fastest ($N=1$) and slowest ($N=1750$) runs. Small deviations exist for low sample sizes.} + \label{fig:walltimes} +\end{figure} + +\section{Conclusions} +This work set out to reconstruct a Tracy-Widom distribution via the direct sampling of calculated eigenvalues of Gaussian orthogonal ensembles. A code leveraging MPI for distributed-memory parallelism and the MKL BLAS library for high-performance numerical methods was used to sample various numbers of ensembles, sizes of matrices, and various other factors to generate data and draw conclusions. While the worker-manager structure worked well for the batch computing of eigenvalues, the statistical results proved inconclusive. It can be said with confidence that the resulting distribution was non-Gaussian but it was not necessarily a Tracy-Widom distribution. This is because of the statistical testing, consisting of the skewness and excess kurtosis, were not in support of a Tracy-Widom distribution. The discrepancies showed at least one trend divergent to the expected value and therefore it is unlikely that further sampling of eigenvalues would mitigate this issue. Rather, it is likely that there is an inconsistency related to transforming the eigenvalues to fit the standard Tracy-Widom. The wall time scaling, however, was consistent with expectations and was invested with respect to both matrix and ensemble size. + \bibliographystyle{ieeetr} \bibliography{refs.bib} \end{document} - - |