commit b37f286f4123d22a0c74a47293f035a2543ceda9
parent b6addfea6e06a8979fd11ee07847514ac9e8fe74
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Sat, 29 Oct 2016 18:12:12 +0300
Add text from ARMA technical report.
Diffstat:
| bib/refs.bib | | | 67 | +++++++++++++++++++------------------------------------------------ |
| phd-diss.org | | | 314 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- |
2 files changed, 330 insertions(+), 51 deletions(-)
diff --git a/bib/refs.bib b/bib/refs.bib
@@ -152,6 +152,17 @@
publisher = {Springer}
}
+@Article{ boccotti1983wind,
+ title = {On wind wave kinematics},
+ author = {Boccotti, Paolo},
+ journal = {Meccanica},
+ volume = {18},
+ number = {4},
+ pages = {205--216},
+ year = {1983},
+ publisher = {Springer}
+}
+
@Article{ bogdanov2015hybrid,
title = {Running applications on a hybrid cluster},
author = {Bogdanov, A. and Gankevich, I. and Gayduchok V. and
@@ -322,6 +333,14 @@
publisher = {Springer}
}
+@Book{ box1976time,
+ title = {Time series analysis: forecasting and control, revised
+ ed},
+ author = {Box, George EP and Jenkins, Gwilym M},
+ year = {1976},
+ publisher = {Holden-Day}
+}
+
@Article{ brunekreef1996design,
title = {Design and analysis of dynamic leader election protocols
in broadcast networks},
@@ -430,24 +449,6 @@
category = {oceanwaves}
}
-###InProceedings{ degtyarev2011effi,
- address = {Yerevan, Armenia},
- author = {Degtyarev, A. and Gankevich, I.},
- booktitle = {Proceedings of 8\textsuperscript{th} International
- Conference ``Computer Science \& Information Technologies''},
- language = {english},
- pages = {248--251},
- rawentry = {Degtyarev A., Gankevich I. Efficiency Comparison of Wave
- Surface Generation Using {OpenCL}, {OpenMP} and {MPI} //
- Proceedings of 8\textsuperscript{th} International
- Conference ``Computer Science \& Information Technologies''
- -- Yerevan, Armenia, -- 2011. -- P. 248-251},
- title = {Efficiency Comparison of Wave Surface Generation Using
- {OpenCL}, {OpenMP} and {MPI}},
- year = {2011},
- category = {oceanwaves}
-}
-
@Article{ degtyarev2011modelling,
title = {Modelling of incident waves near the ship’s hull
(application of autoregressive approach in problems of
@@ -1012,16 +1013,6 @@
publisher = {Springer}
}
-###InCollection{ kochman2012batched,
- title = {Batched transactions for {RESTful} web services},
- author = {Kochman, Sebastian and Wojciechowski, Pawe{\l} T and
- Kmieciak, Mi{\l}osz},
- booktitle = {Current Trends in Web Engineering},
- pages = {86--98},
- year = {2012},
- publisher = {Springer}
-}
-
@Article{ lakshman2010cassandra,
title = {Cassandra: A decentralized structured storage system},
author = {Lakshman, Avinash and Malik, Prashant},
@@ -1057,19 +1048,6 @@
organization = {IEEE}
}
-###InProceedings{ lifflander2014scalable,
- title = {Scalable replay with partial-order dependencies for
- message-logging fault tolerance},
- author = {Lifflander, Jonathan and Meneses, Esteban and Menon,
- Harshitha and Miller, Phil and Krishnamoorthy, Sriram and
- Kal{\'e}, Laxmikant V},
- booktitle = {IEEE International Conference on Cluster Computing
- (CLUSTER)},
- pages = {19--28},
- year = {2014},
- organization = {IEEE}
-}
-
@Article{ longuet1957statistical,
title = {The statistical analysis of a random, moving surface},
author = {Longuet-Higgins, Michael S},
@@ -1408,13 +1386,6 @@
publisher = {Springer Science \& Business Media}
}
-###Book{ wilde2011rest,
- title = {{REST}: from research to practice},
- author = {Wilde, Erik and Pautasso, Cesare},
- year = {2011},
- publisher = {Springer Science \& Business Media}
-}
-
@InProceedings{ zotkin1999job,
title = {Job-length estimation and performance in backfilling
schedulers},
diff --git a/phd-diss.org b/phd-diss.org
@@ -4,13 +4,17 @@
#+LANGUAGE: en
#+LATEX_CLASS: gost
#+LATEX_CLASS_OPTIONS: [hidelinks,fontsize=14pt,paper=a4,pagesize,DIV=calc]
-#+LATEX_HEADER: \IfFileExists{./preamble.tex}{\input{preamble}}{}
+#+LATEX_HEADER: \IfFileExists{./preamble.tex}{\input{preamble}
#+LATEX_HEADER: \organization{Saint Petersburg State University}
#+LATEX_HEADER: \manuscript{}
#+LATEX_HEADER: \degree{thesis for candidate of sciences degree}
#+LATEX_HEADER: \speciality{Speciality 05.13.18\\Mathematical modeling, numerical methods and programme complexes}
#+LATEX_HEADER: \supervisor{Supervisor\\Alexander Degtyarev}
-#+OPTIONS: todo:nil title:nil H:5
+#+LATEX_HEADER: }{}
+#+LATEX_HEADER: \newcommand{\Fourier}[1]{\mathcal{F}\left\{#1\right\}}
+#+LATEX_HEADER: \newcommand{\InverseFourier}[1]{\mathcal{F}^{-1}\left\{#1\right\}}
+#+LATEX_HEADER: \newcommand{\Var}[1]{\sigma_{#1}^2}
+#+OPTIONS: todo:nil title:nil ':t H:5
#+begin_latex
\clearpage
@@ -28,7 +32,7 @@
* Problem statement
* Related work
* ARMA model for ocean wave simulation
-** The reasons for the creation of a new ocean simulation model
+** The reasons for the search for a new ocean simulation model
ARMA model emerged in response to difficulties encountered by practitioners who
used wave simulation models developed in the framework of linear wave theory.
The problems they have encountered in their work can be summarised as the
@@ -52,18 +56,322 @@ following.
** The shape of ACF for different types of waves
*** Two methods to find ocean wave's ACF
**** Analytic method of finding the ACF.
+The simplest way to find auto-covariate function for a particular ocean wave
+profile is to apply Wiener---Khinchin theorem. According to this theorem the
+autocorrelation $K$ of a function $\zeta$ is given by the Fourier transform of
+the absolute square of the function:
+\begin{equation}
+ K(t) = \Fourier{\left| \zeta(t) \right|^2}.
+ \label{eq:wiener-khinchin}
+\end{equation}
+When $\zeta$ is replaced with actual wave profile, this formula gives you
+analytic expression for the corresponding ACF.
+
+For three-dimensional wave profile (2D in space and 1D in time) analytic
+expression is a polynomial of high order and is best obtained via computer
+algebra software. Then for practical usage it can be approximated by
+superposition of exponentially decaying cosines (which is how ACF of a
+stationary ARMA process looks like cite:box1976time).
+
**** Empirical method of finding the ACF.
+However, for three-dimensional case there exists simpler empirical method which
+does not require sophisticated software to determine shape of the ACF. It is
+known that ACF represented by exponentially decaying cosines of a wave profile
+satisfies first order Stokes' equations for gravity waves cite:boccotti1983wind.
+So, if the shape of the wave profile is the only concern, then one can simply
+multiply it by a decaying exponent to get appropriate ACF. This ACF will not
+reflect other wave profile parameters such as wave height and period, but opens
+possibility to simulate waves of a particular non-analytic shape by "drawing"
+their profile, then multiplying it by an exponent and using the resulting
+function as ACF. So, this empirical method is imprecise but offers simpler
+alternative to Wiener---Khinchin theorem; it is mainly useful to test ARMA
+model.
+
*** Examples of ACFs for various types of wave profiles
**** Standing wave.
+For three-dimensional standing wave the profile is approximated by
+\begin{equation}
+ \zeta(t, x, y) = A \sin (k_x x + k_y y) \sin (\sigma t).
+ \label{eq:standing-wave}
+\end{equation}
+In order to get ACF via analytic method one needs to multiply this expression by
+a decaying exponent, because Fourier transform is defined for a function $f$ that
+$f \underset{x \rightarrow \pm \infty}{\longrightarrow} 0$. The formula of the
+profile then transforms to
+\begin{equation}
+ \zeta(t, x, y) =
+ A
+ \exp\left[-\alpha (|t|+|x|+|y|) \right]
+ \sin (k_x x + k_y y) \sin (\sigma t).
+ \label{eq:decaying-standing-wave}
+\end{equation}
+Them, if one takes 3D Fourier transform of this expression via any capable
+computer algebra software, the resulting polynomial may be fitted to the
+following ACF approximation.
+\begin{equation}
+ K(t,x,y) =
+ \gamma
+ \exp\left[-\alpha (|t|+|x|+|y|) \right]
+ \cos \beta t
+ \cos \left[ \beta x + \beta y \right].
+ \label{eq:standing-wave-acf}
+\end{equation}
+So, after applying Wiener---Khinchin theorem we get the same formula but with
+sines replaced with cosines. This replacement is important because the value of
+ACF at $(0,0,0)$ equals to the variance of wave elevation, and if one used sines
+the value would be wrong.
+
+If one tries to replicate the same formula via empirical method, the usual way
+is to adapt eqref:eq:decaying-standing-wave to match eqref:eq:standing-wave-acf.
+This can be done by changing the phase of the sine, or by replacing sine with
+cosine to move the maximum of the function to $(0,0,0)$.
+
**** Propagating wave.
+Three-dimensional profile of this type of wave is approximated by
+\begin{equation}
+ \zeta(t, x, y) = A \cos (\sigma t + k_x x + k_y y).
+ \label{eq:propagating-wave}
+\end{equation}
+For the analytic method one may repeat steps from the previous two paragraphs
+with ACF approximated by
+\begin{equation}
+ K(t,x,y) =
+ \gamma
+ \exp\left[-\alpha (|t|+|x|+|y|) \right]
+ \cos\left[\beta (t+x+y) \right].
+ \label{eq:propagating-wave-acf}
+\end{equation}
+For the empirical method propagating wave profile is simply multiplied by
+a decaying exponent without need to adapt the maximum value of ACF.
+
*** Comparison of studied methods
+To summarise, the analytic method of finding ocean wave's ACF reduces to the
+following steps:
+- Make wave profile decay when approach $\pm \infty$ by multiplying it by
+ a decaying exponent.
+- Take Fourier transform of absolute square of the decaying wave profile using
+ computer algebra software.
+- Fit the resulting polynomial to the appropriate ACF approximation.
+
+Two examples in this section showed that in case of standing and propagating
+waves their decaying profiles resemble the corresponding ACFs with the exception
+that the origin should be moved to the function's maximal value for the ACF to
+be useful in ARMA model simulations. So, using the empirical method the ACF is
+found in the following steps:
+- Make wave profile decay when approach $\pm \infty$ by multiplying it by
+ a decaying exponent.
+- Move maximum value to the origin by adjusting phases or using trigonometric
+ identities to shift the phase of the resulting function.
+
** Governing equations for 3-dimensional ARMA process
*** Three possible processes
+Three-dimensional autoregressive moving average process is defined by
+\begin{equation}
+ \zeta_{i,j,k} =
+ \sum\limits_{l=0}^{p_1}
+ \sum\limits_{m=0}^{p_2}
+ \sum\limits_{n=0}^{p_3}
+ \Phi_{l,m,n} \zeta_{i-l,j-m,k-n}
+ +
+ \sum\limits_{l=0}^{q_1}
+ \sum\limits_{m=0}^{q_2}
+ \sum\limits_{n=0}^{q_3}
+ \Theta_{l,m,n} \epsilon_{i-l,j-m,k-n}
+ ,
+ \label{eq:arma-process}
+\end{equation}
+where $\zeta$ --- wave elevation, $\Phi$ --- AR coefficients, $\Theta$ --- MA
+coefficients, $\epsilon$ --- white noise with Gaussian distribution,
+$(p_1,p_2,p_3)$ --- AR process order, $(q_1,q_2,q_3)$ --- MA process order, and
+$\Phi_{0,0,0} \equiv 0$, $\Theta_{0,0,0} \equiv 0$. The input parameters are
+AR/MA process coefficients and order.
+
**** Autoregressive (AR) process.
+The coefficients $\Phi$ are calculated from ACF via three-dimensional
+Yule---Walker equations:
+\begin{equation*}
+ \Gamma
+ \left[
+ \begin{array}{l}
+ \Phi_{0,0,0}\\
+ \Phi_{0,0,1}\\
+ \vdotswithin{\Phi_{0,0,0}}\\
+ \Phi_{p_1,p_2,p_3}
+ \end{array}
+ \right]
+ =
+ \left[
+ \begin{array}{l}
+ K_{0,0,0}-\Var{\epsilon}\\
+ K_{0,0,1}\\
+ \vdotswithin{K_{0,0,0}}\\
+ K_{p_1,p_2,p_3}
+ \end{array}
+ \right],
+ \qquad
+ \Gamma=
+ \left[
+ \begin{array}{llll}
+ \Gamma_0 & \Gamma_1 & \cdots & \Gamma_{p_1} \\
+ \Gamma_1 & \Gamma_0 & \ddots & \vdotswithin{\Gamma_0} \\
+ \vdotswithin{\Gamma_0} & \ddots & \ddots & \Gamma_1 \\
+ \Gamma_{p_1} & \cdots & \Gamma_1 & \Gamma_0
+ \end{array}
+ \right],
+\end{equation*}
+where $\vec N = \left( p_1, p_2, p_3 \right)$, $\Var{\epsilon}$ --- white noise
+variance, and
+\begin{equation*}
+ \Gamma_i =
+ \left[
+ \begin{array}{llll}
+ \Gamma^0_i & \Gamma^1_i & \cdots & \Gamma^{p_2}_i \\
+ \Gamma^1_i & \Gamma^0_i & \ddots & \vdotswithin{\Gamma^0_i} \\
+ \vdotswithin{\Gamma^0_i} & \ddots & \ddots & \Gamma^1_i \\
+ \Gamma^{p_2}_i & \cdots & \Gamma^1_i & \Gamma^0_i
+ \end{array}
+ \right]
+ \qquad
+ \Gamma_i^j=
+ \left[
+ \begin{array}{llll}
+ K_{i,j,0} & K_{i,j,1} & \cdots & K_{i,j,p_3} \\
+ K_{i,j,1} & K_{i,j,0} & \ddots &x \vdotswithin{K_{i,j,0}} \\
+ \vdotswithin{K_{i,j,0}} & \ddots & \ddots & K_{i,j,1} \\
+ K_{i,j,p_3} & \cdots & K_{i,j,1} & K_{i,j,0}
+ \end{array}
+ \right],
+\end{equation*}
+Since $\Phi_{0,0,0}\equiv0$, the first row and column of $\Gamma$ can be
+eliminated. Matrix $\Gamma$ is block-toeplitz, positive definite and symmetric,
+hence the system is solved by Cholesky decomposition. White noise variance is
+estimated by
+\begin{equation*}
+ \Var{\epsilon} =
+ K_{0,0,0}
+ -
+ \sum\limits_{i=0}^{p_1}
+ \sum\limits_{i=0}^{p_2}
+ \sum\limits_{k=0}^{p_3}
+ \Phi_{i,j,k} K_{i,j,k}.
+\end{equation*}
+
**** Moving average (MA) process.
+The coefficients $\Theta$ are calculated from ACF via the following non-linear
+system of equations:
+\begin{equation*}
+ K_{i,j,k} =
+ \left[
+ \displaystyle
+ \sum\limits_{l=i}^{q_1}
+ \sum\limits_{m=j}^{q_2}
+ \sum\limits_{n=k}^{q_3}
+ \Theta_{l,m,n}\Theta_{l-i,m-j,n-k}
+ \right]
+ \Var{\epsilon},
+\end{equation*}
+which is solved by fixed-point iteration method via the following formulae
+\begin{equation*}
+ \theta_{i,j,k} =
+ -\frac{K_{0,0,0}}{\Var{\epsilon}}
+ +
+ \sum\limits_{l=i}^{q_1}
+ \sum\limits_{m=j}^{q_2}
+ \sum\limits_{n=k}^{q_3}
+ \Theta_{l,m,n} \Theta_{l-i,m-j,n-k}
+\end{equation*}
+Coefficients are updated from back to front: from
+$(i,j,k) = (q_1,q_2,q_3)$ to $(i,j,k) = (0,0,0)$. White noise variance is
+estimated by
+\begin{equation*}
+ \Var{\epsilon} = \frac{K_{0,0,0}}{
+ 1
+ +
+ \sum\limits_{i=0}^{q_1}
+ \sum\limits_{i=0}^{q_2}
+ \sum\limits_{k=0}^{q_3}
+ \Theta_{i,j,k}^2
+ }.
+\end{equation*}
+
**** Mixed autoregressive moving average (ARMA) process.
+Generally speaking, formulae for mixed process are the same as for AR and MA
+part, but there are several approaches to mix them.
+- The approach proposed in~\cite{box1976time} which involves dividing ACF into
+ MA and AR part is not applicable here, because in three dimensions the
+ division is not possible: there always be parts of the ACF that are not taken
+ into account by AR and MA process.
+- The alternative approach is to use the same (undivided) ACF for both AR and MA
+ part but use different process order, however, then realisation
+ characteristics (mean, variance etc.) become skewed: these are characteristics
+ of the two overlapped processes.
+For the first approach there is a formula to recompute ACF for AR part to make
+the mixed process correspond to the initial ACF, but there is no such formula
+for the second approach. So, the best solution for now is to simply use AR and
+MA process exclusively.
+
*** Process selection criteria for different wave profiles
+The main problem of ARMA model application to ocean wave generation is that for
+different types of wave profiles different processes must be used: standing
+waves can only be generated by AR process, and propagating waves can only be
+generated by MA process. This statement comes from practice: if one tries to use
+the processes the other way round, the resulting realisation either diverges or
+does not look like real ocean waves. (The latter happens for non-invertible MA
+process, and sometimes for AR process for unknown reason.) So, the best way to
+apply ARMA model to ocean wave generation is to use AR process for standing
+waves and MA process for progressive waves.
+
+The other problem of three-dimensional AR and MA processes in this context is
+inability to determine the number of coefficients from ACF. For one-dimensional
+processes this can be achieved via iterative methods, but their formulae need to
+be mapped to three-dimensions, otherwise they do not converge.
+
+The final problem is how to mix 3-dimensional AR and MA processes. Again the new
+formula to recompute ACF needs to be derived in case of three dimensions.
+
+It appears that some statements made for AR and MA processes in cite:box1976time
+should be flipped for three-dimensional case. For example, the authors say that
+ACF of MA process is cut at $(q_1,q_2,q_3)$ and ACF of AR process decays to
+nought infinitely, but in practice making ACF of 3-dimensional MA process not
+decay results in it being non-invertible and producing realisation that does not
+look like real ocean waves, whereas doing the same for ACF of AR process does
+not have severe consequences. The second example: the authors say that one
+should allocate the first $q$ points of ACF to MA process (as it often needed to
+describe the peaks in ACF) and leave the rest points to AR process, but in
+practice in case of ACF of propagating wave AR process is stationary only for
+the first time slice of the ACF, and the rest is left to MA process.
+
** Verification of wavy surface integral characteristics
+Research shows that several ocean wave characteristics (e.g. wave height, wave
+period, wave length etc.) have Weibull distribution differing only in shape
+parameter (tab. [[tab:weibull-shape]]), and wave elevation has Gaussian
+distribution. In order to verify that distributions corresponding to generated
+realisation are correct, we use quantile-quantile plots (plots where analytic
+quantile values are used for X axis and estimated quantile values for Y axis).
+If the estimated distribution matches analytic then the graph is the straight
+line. Tails of the graph may diverge from the straight line, because they can
+not be reliably estimated from the realisation. Different methods of extracting
+waves from realisation produce variations in quantile function tails, it is
+probably impractical to extract every possible wave from realisation since they
+may (and often) overlap.
+
+#+name: tab:weibull-shape
+#+caption: Values of Weibull shape parameter for different wave characteristics.
+#+attr_latex: :booktabs t
+| Characteristic | Weibull shape ($k$) |
+|----------------------+---------------------|
+| Wave height | 2 |
+| Wave length | 2.3 |
+| Crest length | 2.3 |
+| Wave period | 3 |
+| Wave slope | 2.5 |
+| Three-dimensionality | 2.5 |
+
+Verification was performed for standing and propagating waves. The corresponding
+ACFs and quantile-quantile plots of wave characteristics distributions are shown
+in fig.
+\cref{fig:acf-plots,fig:standing-wave-distributions,fig:propagating-wave-distributions}.
+
** Modeling non-linearity of ocean waves
** Non-physical nature of ARMA model
ARMA model, owing to its non-physical nature, does not have the notion of ocean
