\section*{Notes and References}\addcontentsline{toc}{section}{Notes and References}\markright{Notes and References}
\begin{small}\addtolength{\baselineskip}{-1.0pt}\parindent 0pt \parskip 4pt}{\clearpage\end{small}\addtolength{\baselineskip}{1.0pt}}
\newcommand{\nrsection}[1]{\subsection*{#1}}
\newcommand{\nrsubsection}[1]{\subsubsection*{#1}}

\newcounter{exno}
\renewcommand{\theexno}{\thechapter.\arabic{exno}}
\newenvironment{exercises}{\clearpage\section*{Exercises}\addcontentsline{toc}{section}{Exercises}\markright{Exercises}
\begin{small}\addtolength{\baselineskip}{-1.0pt}
\renewcommand{\labelenumi}{(\alph{enumi})}
\begin{list} {{\bf Exercise \thechapter.\arabic{exno}.}}
{\usecounter{exno
}}{\end{list}\clearpage\end{small}\addtolength{\baselineskip}{1.0pt}}

\iffalse
\newenvironment{example}%
{\begin{quote}\begin{small}\textbf{Example.}}%
{\end{small}\end{quote}}

\newenvironment{examples}%
{\begin{quote}\begin{small}\textbf{Examples.}}%
{\end{small}\end{quote}}

\newenvironment{remark}%
{\begin{quote}\begin{small}\textbf{Remark.}}%
{\end{small}\end{quote}}
\fi

\newenvironment{proof}{\textbf{Proof.}}{~~\rule[-1pt]{6pt}{6pt}}\def\QED{\QED\bigskip}

\newenvironment{algdesc}%
{\begin{quote}}{\end{quote}}

\def\figbox#1{\framebox[\hsize]{\hfil\parbox{0.9\hsize}{#1}}}

\makeatletter
\long\def\@makecaption#1#2{
   \vskip 9pt
   \begin{small}
   \setbox\@tempboxa\hbox{{\bf #1:} #2}
   \ifdim \wd\@tempboxa > 5.5in
        \begin{center}
        \begin{minipage}[t]{5.5in}
        \addtolength{\baselineskip}{-0.95pt}
        {\bf #1:} #2 \par
        \addtolength{\baselineskip}{0.95pt}
        \end{minipage}
        \end{center}
   \else
    \hbox to\hsize{\hfil\box\@tempboxa\hfil}
   \fi
   \end{small}\par
}
\makeatother

\newcounter{oursection}
\newcommand{\oursection}[1]{
 \addtocounter{oursection}{1}
 \setcounter{equation}{0}
 \clearpage \begin{center} {\Huge\bfseries #1} \end{center}
 {\vspace*{0.15cm} \hrule height.3mm} \bigskip
 \addcontentsline{toc}{section}{#1}
}
\newcommand{\oursectionf}[1]{
 \addtocounter{oursection}{1}
 \setcounter{equation}{0}
 \foilhead[-.5cm]{#1 \vspace*{0.8cm} \hrule height.3mm }
 \LogoOn
}
\newcommand{\oursectionfl}[1]{
 \addtocounter{oursection}{1}
 \setcounter{equation}{0}
 \foilhead[-1.0cm]{#1}
 \LogoOn
}

\newcounter{lecture}
\newcommand{\lecture}[1]{
 \addtocounter{lecture}{1}
 \setcounter{equation}{0}
 \setcounter{page}{1}
 \renewcommand{\theequation}{\arabic{equation}}
 \renewcommand{\thepage}{\arabic{lecture} -- \arabic{page}}
 \raggedright \sffamily \LARGE
 \cleardoublepage\begin{center}
 {\Huge\bfseries Lecture \arabic{lecture} \bigskip \\ #1}\end{center}
 {\vspace*{0.15cm} \hrule height.3mm} \bigskip
 \addcontentsline{toc}{chapter}{\protect\numberline{\arabic{lecture}}{#1}}
 \pagestyle{myheadings}
 \markboth{Lecture \arabic{lecture}}{#1}
}
\newcommand{\lecturef}[1]{
 \addtocounter{lecture}{1}
 \setcounter{equation}{0}
 \setcounter{page}{1}
 \renewcommand{\theequation}{\arabic{equation}}
 \renewcommand{\thepage}{\arabic{lecture}--\arabic{page}}
 \parindent 0pt
 \MyLogo{#1}
 \rightfooter{\thepage}
 \leftheader{}
 \rightheader{}
 \LogoOff
 \begin{center}
 {\large\bfseries Lecture \arabic{lecture} \bigskip \\ #1}
 \end{center}
 {\vspace*{0.8cm} \hrule height.3mm}
 \bigskip
}
\newcommand{\lecturefl}[1]{
 \addtocounter{lecture}{1}
 \setcounter{equation}{0}
 \setcounter{page}{1}
 \renewcommand{\theequation}{\arabic{equation}}
 \renewcommand{\thepage}{\arabic{lecture}--\arabic{page}}
 \addtolength{\topmargin}{-1.5cm}
 \raggedright
 \parindent 0pt
 \rightfooter{\thepage}
 \leftheader{}
 \rightheader{}
 \LogoOff
 \begin{center}
 {\Large \bfseries Lecture \arabic{lecture} \\*[\bigskipamount] {#1}}
 \end{center}
 \MyLogo{#1}
}

\section{Introduction}
We consider the problem of estimating a covariance matrix from sample multivariate data by maximizing its likelihood, while penalizing the inverse covariance so that its graph is {\em sparse}. This problem is known as covariance selection and can be traced back at least to \citet{Demp72}. The coefficients of the inverse covariance matrix define the representation of a particular Gaussian distribution as a member of the exponential family, hence sparse maximum likelihood estimates of the inverse covariance yield sparse representations of the model in this class. Furthermore, in a Gaussian model, zeros in the inverse covariance matrix correspond to {\em conditionally} independent variables, so this penalized maximum likelihood procedure simultaneously stabilizes estimation and isolates {\em structure} in the underlying graphical model (see \citet{Laur96}).

Given a sample covariance matrix $\Sigma \in \symm_n$, the covariance selection problem is written as follows
\[\begin{array}{ll}
\mbox{maximize} &  \log \det X -  \mathop{\bf Tr} (\Sigma X) - \rho \mathop{\bf Card}(X)
\end{array}\]
in the matrix variable $X\in\symm_n$, where $\rho>0$ is a penalty parameter controlling sparsity and $\mathop{\bf Card}(X)$ is the number of nonzero elements in $X$. This is a combinatorially hard (non-convex) problem and, as in \citet{Dahl08,Bane06,Dahl05a}, we form the following convex relaxation
\begin{equation}\label{eq:covsel-intro}
\begin{array}{ll}
\mbox{maximize}  &  \log \det X -  \mathop{\bf Tr} (\Sigma X) - \rho \|X\|_1
\end{array}\end{equation}
which is a convex problem in the matrix variable $X\in\symm_n$, where $\|X\|_1$ is the sum of absolute values of the coefficients of $X$ here. After scaling, the $\|X\|_1$ penalty can be understood as a convex lower bound on $\mathop{\bf Card}(X)$. Another completely different approach derived in \citet{Mein06} reconciles the local dependence structure inferred from $n$ distinct $\ell_1$-penalized regressions of a single variable against all the others. Both this approach and the convex relaxation (\ref{eq:covsel-intro}) have been shown to be consistent in \citet{Mein06} and \citet{Bane08} respectively.

In practice however, both methods are computationally challenging when $n$ gets large. Various algorithms have been employed to solve (\ref{eq:covsel-intro}) with~\citet{Dahl05a} using a custom interior point method and~\citet{Bane08} using a block coordinate descent method where each iteration required solving a LASSO-like problem, among others. This last method is efficiently implemented in the GLASSO package by \citet{Frie07} using coordinate descent algorithms from \citet{Frie07b} to solve the inner regression problems.

One key issue in all these methods is that there is no a priori obvious choice for the penalty parameter. In practice, at least a partial regularization path of solutions has to be computed, and this procedure is then repeated many times to get confidence bounds on the graph structure by cross-validation. Pathwise LASSO algorithms such as LARS by \citep{Efro04} can be used to get a full regularization path of solution using the method in \citet{Mein06} but this still requires solving and reconciling $n$ regularization paths on regression problems of dimension~$n$.

Our contribution here is to formulate a pathwise algorithm for solving problem (\ref{eq:covsel-intro}) using numerical continuation methods (see \cite{Bach05} for an application in kernel learning). Each iteration requires solving a large structured linear system (predictor step) then improving precision using a block coordinate descent method (corrector step). Overall, the cost of moving from one solution to problem (\ref{eq:covsel-intro}) to another is typically much lower than that of solving two separate instances of (\ref{eq:covsel-intro}). We also derive a coordinate descent algorithm for solving the corrector step, where each iteration is closed-form and requires only solving a cubic equation. We illustrate the performance of our methods on several artificial and realistic data sets.

The paper is organized as follows. Section \ref{s:covsel} reviews some basic convex optimization results on the covariance selection problem in (\ref{eq:covsel-intro}). Our main pathwise algorithm is described in Section \ref{s:algo}. Finally, we present some numerical results in Section \ref{s:numres}.

\paragraph{Notation.} In what follows, we write $\symm_n$ for the set of symmetric matrices of dimension $n$. For a matrix $X\in{\mbox{\bf R}}^{m\times n}$, we write $\|X\|_F$ its Frobenius norm, $\|X\|_1=\sum_{ij}|X_{ij}|$ the $\ell_1$ norm of its vector of coefficients, and $\mathop{\bf Card}(X)$ the number of nonzero coefficients in $X$.

\section{Covariance Selection}
\label{s:covsel} Starting from the convex relaxation defined above
\begin{equation}\label{eq:covsel}
\begin{array}{ll}
\mbox{maximize}  &  \log \det X -  \mathop{\bf Tr} (\Sigma X) - \rho \|X\|_1
\end{array}\end{equation}
 in the variable  $X\in{\symm_n}$, where $\|X\|_1$ can be understood as a convex lower bound on the $\mathop{\bf Card}(X)$ function whenever $|X_{ij}|\leq 1$ (we can always scale $\rho$ otherwise). Let us write $X^\ast(\rho)$ for the optimal solution of problem (\ref{eq:covsel}). In what follows, we will seek to compute (or approximate) the entire regularization path of solutions $X^\ast(\rho)$, for $\rho \in {\mbox{\bf R}}_+$. To remove the nonsmooth penalty, we can set $X=L-M$ and rewrite the problem above as
\begin{equation}\label{eq:covsel-primal}
\begin{array}{ll}
\mbox{maximize}  & \log \det (L -M) -  \mathop{\bf Tr} (\Sigma(L-M)) - \rho \mathbf 1^T(L +M)\mathbf 1\\
\mbox{subject to} & L_{ij},M_{ij} \geq 0,\quad i,j=1,\ldots,n,
\end{array}\end{equation}
in the matrix variables $L, M \in \symm_n$. We can form the following dual to problem (\ref{eq:covsel}) as
\begin{equation}\label{eq:covsel-dual}
\begin{array}{ll}
\mbox{minimize} &  -\log \det (U) - n \\
\mbox{subject to} & U_{ij} \leq \Sigma_{ij} + \rho, \quad i,j=1,\ldots,n, \\
                  & U_{ij} \geq \Sigma_{ij} - \rho, ,\quad i,j=1,\ldots,n,
\end{array}\end{equation}
in the variable $U\in\symm_n$. As in \citet{Bach05} for example, in the spirit of barrier methods for interior point algorithms, we then form the following (unconstrained) regularized problem
\begin{equation}\label{eq:regularized}
\min_{U\in\symm_n} -\log \det (U) -  t\left(\sum_{i,j=1}^n \log(\rho +\Sigma_{ij}
-U_{ij})  + \sum_{i,j=1}^n \log (\rho -\Sigma_{ij}+U_{ij})\right)
\end{equation}
in the variable $U \in \symm_n$ and $t > 0$ specifies a desired tradeoff level between centrality (smoothness) and optimality. From every solution $U^\ast(t)$ corresponding to each $t>0$, the barrier formulation also produces an explicit \emph{dual} solution $(L^\ast(t), M^\ast(t))$ to Problem (\ref{eq:covsel-dual}). Indeed we can define matrices  $L, M \in\symm_n$ as follows
\[
L_{ij}(U,\rho) = \frac{t}{\rho+\Sigma_{ij}-U_{ij}} \quad \mbox{and} \quad
M_{ij}(U,\rho) = \frac{t}{\rho-\Sigma_{ij}+U_{ij}}
\]
First order optimality conditions for problem (\ref{eq:regularized}) then imply
\[
(L - M) = U^{-1}.
\]
As $t$ tends to 0, problem (\ref{eq:regularized}) traces a central path towards the optimal solution to problem (\ref{eq:covsel-dual}). If we write $f(U)$ for the objective function of problem (\ref{eq:covsel-dual}) and call $p^\ast$ its optimal value, we get as in \cite[\S11.2.2]{Boyd03}
\[
f(U^\ast(t)) - p^\ast \leq 2n^2t
\]
hence $t$ can be understood as a surrogate duality gap when solving the dual problem (\ref{eq:covsel-dual}).

\section{Algorithm}
\label{s:algo} In this section we derive a Predictor-Corrector algorithm to approximate the entire path of solutions $X^\ast(\rho)$ when $\rho$ varies between 0 and $\max_{i}\Sigma_{ii}$ (beyond which the solution matrix is diagonal). Defining
\[
H(U,\rho) = L(U,\rho) - M(U,\rho) - U^{-1}
\]
we trace the curve $H(U,\rho)=0$, the first order optimality condition for problem (\ref{eq:regularized}). Our pathwise covariance selection algorithm is defined in Algorithm \ref{alg:covpath}.

\begin{algorithm}
\caption{Pathwise Covariance Selection}
\label{alg:covpath}
\begin{algorithmic} [1]
\REQUIRE $\Sigma\in\symm_m$
\STATE Start with $(U_0, \rho_0)$ s.t  $H(U_0,\rho_0) =0$.
\FOR{$i=1$ to $k$}
\STATE\emph{Predictor Step}. Let $\rho_{i+1} = \rho_i + h$. Compute a tangent direction by solving the linear system
\[
\frac{\partial H}{\partial \rho}(U_i,\rho_i) + J(U_i,\rho_i) \frac{\partial U}{\partial\rho} = 0
\]
in $\partial U/\partial \rho\in\symm_n$, where $J(U_i,\rho_i)=\partial H(U,\rho)/\partial U\in\symm_{n^2}$ is the Jacobian matrix of the function $H(U,\rho)$.
\STATE Update $U_{i+1} = U_i + h \partial U/\partial \rho$.
\STATE\emph{Corrector Step}. Solve problem (\ref{eq:regularized}) starting at $U = U_{i+1}$.
\ENDFOR
\ENSURE Sequence of matrices $U_i$, $i=1,\ldots,k$.
\end{algorithmic}
\end{algorithm}

Typically in Algorithm \ref{alg:covpath}, $h$ is a small constant, $\rho_0=\max_{i}\Sigma_{ii}$, and $U_0$ is computed by solving a single (very sparse) instance of problem (\ref{eq:regularized}) for example.

\subsection{Predictor: conjugate Gradient method} \label{ss:pred}
In Algorithm \ref{alg:covpath}, the tangent direction in the predictor step is computed by solving a linear system  $Ax=b$ where $ A = (U^{-1} \otimes U^{-1} + D)$ and $D$ is a diagonal matrix. This system of equations has dimension $n^2$ and we solve it using the conjugate gradient (CG) method.

\paragraph{CG iterations.} The most expensive operation in the CG iterations is the computation of a matrix vector product $Ap_k$, with $p_k \in {\mbox{\bf R}}^{n^2 }$. Here however, we can exploit problem structure to compute this step efficiently. Observe that $(U^{-1} \otimes U^{-1})p_k = \mathop{\bf vec}(U^{-1} P_kU^{-1})$ when $p_k =\mathop{\bf vec}(P_k)$, so the  computation of the matrix vector product $Ap_k$ needs only $O(n^3)$ flops instead of $O(n^4)$. The CG method then needs at most $O(n^2)$ iterations to converge, leading to a total complexity of $O(n^5)$ for the predictor step. In practice, we will observe that CG needs considerably fewer iterations.

\paragraph{Stopping criterion.}
To speed up the computation of the predictor step, we can stop the conjugate gradient solver when the norm of the residual falls below the numerical tolerance $t$. In our experiments here, we stopped the solver after the residual decreases by two order of magnitudes.

\paragraph{Scaling \& warm start.}
Another option, much simpler than the predictor step detailed above, is warm starting. This means simply scaling the current solution to make it feasible for the problem after $\rho$ is updated. In practice, this method turns out to be as efficient as the predictor step as it allows us to follow the path starting from the sparse end (where more interesting solutions are located). Here, we start the algorithm from the sparsest possible solution, a diagonal matrix $U$ such that
\[
U_{ii}=\Sigma_{ii} +(1-\epsilon)\rho_\mathrm{max} I, \quad i=1,\ldots,n,
\]
where $\rho_\mathrm{max}=\max_i \Sigma_{ii}$. Suppose now that iteration $k$ of the algorithm produced a matrix solution $U_k$ corresponding to a penalty $\rho_k$, the algorithm with (lower) penalty $\rho_{k+1}$ is started at the matrix
\[
U=(1-\rho_{k+1}/\rho_{k})\Sigma+(\rho_{k+1}/\rho_{k})U_k
\]
which is a feasible starting point for the corrector problem that follows. This is the method that was implemented in the final version of our code and that is used in the numerical experiments detailed in the numerical section.

\subsection{Corrector: block coordinate descent} \label{ss:corr}
For small size problems, we can use Newton's method to solve problem~(\ref{eq:regularized}). However  from a computational perspective, this approach is not practical for large values of $n$. We can simplify iterations using a block coordinate descent algorithm that updates one row/column of the matrix in each iteration (\citet{Bane08}). Let us partition the matrices $U$ and $\Sigma$ as
\[
U = \left(\begin{array}{cc}V&u\\
u^T&w\end{array}\right)
\quad \mbox{and} \quad
S = \left(\begin{array}{cc}A&b\\
b^T&c\end{array}\right)
\]
We keep $V$ fixed in each iteration and solve for $u$ and $w$. Without loss of generality, we can always assume that we are updating the last row/column.
\paragraph{Algorithm.} Problem (\ref{eq:regularized}) can be written in block format as:
\begin{equation}\label{eq:block-regularized}
\begin{array}{ll}
\mbox{minimize} & -\log(w -u^TV^{-1}u)  -t(\log(\rho+c-w) +\log (\rho-c+w))\\
\\
& -  2t\left(\sum_{i} \log(\rho+b_i -u_i) + \sum_{i} \log(\rho -b_{i}+u_{i})\right)
\end{array}
\end{equation}
in the variables $u \in {\mbox{\bf R}}^{(n-1)}$ and $w \in {\mbox{\bf R}}$. Here  $V \in\symm^{(n-1)}$ is kept fixed in each iteration.
\begin{algorithm}
\caption{Block coordinate descent corrector steps}
\label{alg:block-corr}
\begin{algorithmic} [1]
\REQUIRE $U_0,~\Sigma\in\symm_n$
\FOR{$i=1$ to $k$}
\STATE Pick the row and column to update.
\STATE Solve the inner problem (\ref{eq:block-regularized}) using coordinate descent (each coordinate descent step requires solving a cubic equation).
\STATE Update $U^{-1}$.
\ENDFOR
\ENSURE A matrix $U_k$ solving (\ref{eq:regularized}).
\end{algorithmic}
\end{algorithm}
We use the Sherman-Woodbury-Morrison (SWM) formula (see \citet[\S C.4.3]{Boyd03}) to efficiently update $U^{-1}$ at each iteration, so it suffices to compute the full inverse only once at the beginning of the path. The choice and order of row/column updates significantly affects performance. Although predicting the effect of a whole~$i^{th}$ row/column update is numerically expensive, we use the fact that the impact of updating diagonal coefficients usually dominates all others and can be computed explicitly at a very low computational cost. It corresponds to the maximum improvement in the dual objective function that can be achieved by updating the current solution $U$ to $U + w e_ie_i^T $, where $e_i$ is the~$i^{th}$ unit vector. The objective function value is a decreasing function of $w$ and $w$ must be lower than $\rho+\Sigma_{ii}-U_{ii}$ to preserve dual feasibility, so updating the $i^{th}$ diagonal coefficient will decrease the objective by $\delta_i=(\rho + \Sigma_{ii}-U_{ii})U^{-1}_{ii}$ after minimizing over $w$. In practice, updating the top 10\% row/columns with largest~$\delta$ is often enough to reach our precision target and very significantly speeds-up computations. We also solve the inner problem (\ref{eq:block-regularized}) by a coordinate descent method (as in \citet{Frie07b}), taking advantage of the fact that a point minimizing (\ref{eq:block-regularized}) over a single coordinate can be computed in closed-form by solving a cubic equation. Suppose $(u,w)$ is the current point and that we wish to optimize coordinate $u_j$ of the vector $u$, we define
\begin{equation}\label{eq:coefs}
\begin{array}{ll}
\alpha = - V^{-1}_{jj} \\
\beta = -2u_j(\sum_{k\neq j} V^{-1}_{kj}u_k) \\
\gamma =  w - u^TV^{-1}u - \alpha u_j - \beta u_j^2
\end{array}\end{equation}
The optimality conditions imply that the the optimal $u_j^\ast$ must satisfy the following cubic equation
\begin{equation}\label{eq:cubic}
\begin{array}{ll}
p_1x^3 + p_2x^2 +p_3x +  p_4= 0
\end{array}\end{equation}
where
\[\begin{array}{ll}
p_1 = 2(1+2t)\alpha,~p_2 = (1+4t)\beta - 4(1+2t)\alpha b_j \\
p_3 = 4t\gamma  - 2(1+2t)\beta b_j    + 2\alpha(b^2_j -2\rho^2),~p_4 = \beta(b^2_j-\rho^2) -4t\gamma b_j.
\end{array}\]
Similarly the diagonal update  $w$ satisfies the following quadratic equation.
\[\begin{array}{ll}
(1+2t)w^2 -2( t(u^TV^{-1}u) +c(1+t))w + c^2 -\rho^2 + 2tc(u^TV^{-1}u) = 0
\end{array}\]
Here too, the order in which we optimize the coordinates has a significant impact.

\paragraph{Dual block problem.} We can derive a dual to problem (\ref{eq:block-regularized}) by rewriting it as a constrained optimization problem to get
\begin{equation}\label{eq:dummy-block-regularized}
\begin{array}{ll}
\mbox{minimize} & -\log x_1 -t(\log x_2 +\log x_3) -  2t\left(\sum_{i} (\log y_i + \log z_i) \right)\\
\mbox{subject to}  & x_1 \leq  w - u^TV^{-1}u \\
                               & x_2 = \rho + c -w,~x_3 = \rho -c +w \\
                               & y_i = \rho +b_i - u_i,~z_i = \rho -b_i +u_i
\end{array}
\end{equation}
in the variables $u \in {\mbox{\bf R}}^{(n-1)}, w \in {\mbox{\bf R}}, x \in {\mbox{\bf R}}^3, y \in {\mbox{\bf R}} ^{(n-1)}, z \in {\mbox{\bf R}}^{(n-1)}$. The dual to problem (\ref{eq:dummy-block-regularized}) is written
\begin{equation}\label{eq:dual-block-regularized}
\begin{array}{ll}
\mbox{maximize} & 1 + 2t(2n-1)+ \log \alpha_1 - \alpha_2(\rho+c) - \alpha_3(\rho-c)\\
& - \sum_{i} \left ( \beta_i(\rho+b_i) + \eta_i(\rho-b_i)\right)\\
                    & + t\log(\alpha_2/t)+t\log(\alpha_3/t) + 2t\left(\sum_i\left(\log(\beta_i/2t) +    \log(\eta_i/2t) \right)\right)\\
\mbox{subject to}  &\alpha_1 = \alpha_2 - \alpha_3 \\
                               & \alpha_1 \geq 0
\end{array}
\end{equation}
in the variables  $\alpha \in {\mbox{\bf R}}^3, \beta \in {\mbox{\bf R}} ^{(n-1)}$ and $\eta \in {\mbox{\bf R}}^{(n-1)}$. Surrogate dual points then produce an explicit stopping criterion.

\subsection{Complexity}
Solving for the predictor step using conjugate gradient as in $\S\ref{ss:pred}$ requires $O(n^2)$ matrix products (at a cost of $O(n^3)$ each) in the worst-case, but the number of iterations necessary to get a good estimate of the predictor is typically much lower (cf. experiments in the next section). Scaling and warm start on the other hand has complexity $O(n^2)$. The inner and outer loops of the corrector step are solved using coordinate descent, with each coordinate iteration requiring the (explicit) solution of a cubic equation.

Results on the convergence of the coordinate descent in the smooth case can be traced back at least to \citep{Luo92} or \citep{Tsen01}, who focus on local linear convergence in the strictly convex case. More precise convergence bounds have been derived in \cite{Nest10} who shows linear convergence (i.e. with complexity growing as $\log(1/\epsilon)$) of a randomized variant of coordinate descent for strongly convex functions, and a complexity bound growing proportionally to $1/\epsilon$ when the gradient is Lipschitz continuous coordinatewise. Unfortunately, because it uses a randomized step selection strategy, the algorithm in its standard form is inefficient in our case here, as it requires too many SWM matrix updates to switch between columns. Optimizing the algorithm in \cite{Nest10} to adapt it to our problem (e.g. by adjusting the variable selection probabilities to account for the relative cost of switching columns) is a potentially promising research direction.

The complexity of our algorithm can be summarized as follows.
\begin{itemize}
\item Because our main objective function is strictly convex, our algorithm converges locally linearly, but we have no explicit bound on the total number of iterations required.
\item Starting the algorithm requires forming the inverse matrix $V^{-1}$ at a cost of $O(n^3)$.
\item Each iteration requires solving a cubic equation for each coordinatewise minimization problem to form the coefficients in (\ref{eq:coefs}), at a cost of $O(n^2)$. Updating the problem to switch from one iteration to the next using SWM updates then costs $O(n^2)$. This means that scanning the full matrix with coordinate descent requires $O(n^4)$ flops.
\end{itemize}
While the lack of precise complexity bound is a clear shortcoming of our choice of algorithm for solving the corrector step, as discussed by \cite{Nest08}, algorithm choices are usually guided by the type of operations (projections, barrier computations, inner optimization problems) that can be solved very efficiently or in closed-form. In our case here, it turns out that coordinate descent iterations can be performed very fast, in closed-form (by solving cubic equations), which seems to provide a clear (empirical) complexity advantage to this technique.

\section{Numerical Results} \label{s:numres}
We compare the numerical performance of several methods for computing a full regularization path of solutions to problem (\ref{eq:covsel}) on several realistic data sets: the senator votes covariance matrix from \citet{Bane06}, the {\it Science} topic model in \citet{Blei07} with 50 topics, the covariance matrix of 20 foreign exchange rates, the UCI SPECTF heart dataset (diagnosing of cardiac images), the UCI LIBRAS hand movement dataset and the UCI HillValley dataset. We compute a path of solutions using the methods detailed here (Covpath) and repeat this experiment using the Glasso path code \citet{Frie07} which restarts the covariance selection problem at $\rho + \epsilon$ at the current solution of (\ref{eq:covsel}) obtained at $\rho$. We also tested the smooth first order code with warm-start ASPG described in \citep{Lu10a} as well as the greedy algorithm SINCO by \citet{Sche09}. Note that the later only identifies good sparsity patterns but does not (directly) produce feasible solutions to problem (\ref{eq:covsel-dual}). Our prototype code here is written in MATLAB (except for a few steps in~C), ASPG and SINCO are also written in MATLAB, while Glasso is compiled from Fortran and interfaced with R. We use the scaling/warm-start approach detailed in \S\ref{s:algo} and scan the full set of variables at each iteration of the block-coordinate descent algorithm (optimizing over the 10\% most promising variables sometimes significantly speeds up computations but is more unstable), so the results reported here describe the behavior of the most robust implementation of our algorithm. We report CPU time (in seconds) versus problem dimension in Table \ref{tab:cpu}.  Unfortunately, Glasso does not use the duality gap as a stopping criterion but rather lack of progress (average absolute parameter change less than $10^{-4}$). Glasso fails to converge on the HillValley example.

\begin{table}[H]
\begin{center}
\begin{tabular}{r|rrrrr}
Dataset & Dimension & Covpath & Glasso & ASPG & SINCO\\
\hline
Interest Rates & 20 & 0.036 & 0.200 & 0.30 & \bf 0.007\\
FXData & 20 & \bf 0.016 & 1.467 & 4.88 & 0.109 \\
Heart & 44 & \bf 0.244 & 2.400 & 11.25 & 5.895\\
ScienceTopics & 50 & \bf 0.026 & 2.626 & 11.58 & 5.233\\
Libras & 91 & \bf 0.060 & 3.329 &  35.80 & 40.690\\
HillValley & 100 & \bf 0.068 & - & 47.22 & 68.815\\
Senator & 102 & \bf 4.003 & 5.208 & 10.44 & 5.092\\
\end{tabular}
\caption{{\small CPU time (in seconds) versus problem type for computing a regularization path for 50 values of the penalty $\rho$, using the path following method detailed here (Covpath), the Glasso code with warm-start (Glasso), the pathwise code (ASPG) in \citep{Lu10a} and the SINCO greedy code by \citet{Sche09}.} \label{tab:cpu}}
\end{center}
\end{table}

As in \cite{Bane08}, to test the behavior of the algorithm on examples with known graphs, we also sample sparse random matrices with Gaussian coefficients, add multiples of the identity to make them positive semidefinite, then use the inverse matrix as our sample matrix~$\Sigma$. We use these examples to study the performance of the various algorithms listed above on increasingly large problems. Computing times are listed in Table~\ref{tab:cpu10}, for a path of length 10, and Table~\ref{tab:cpu50} for a path of length 50. The penalty coefficients $\rho$ are chosen to produce a target sparsity around 10\%.

\begin{table}[H]
\begin{center}
\begin{tabular}{r|rrrr}
Dimension & Covpath & Glasso & ASPG & SINCO\\
\hline
20&\bf0.0042&2.32&0.53&0.22\\
50&\bf0.0037&0.59&4.11&3.80\\
100&\bf0.0154&1.11&13.36&13.58\\
200&\bf0.0882&4.73&73.24&61.02\\
300&\bf0.2035&13.52&271.05&133.99\\
\end{tabular}
\caption{{\small CPU time (in seconds) versus problem dimension for computing a regularization path for 10 values of the penalty $\rho$, using the path following method detailed here (Covpath), the Glasso code with warm-start (Glasso), the pathwise code (ASPG) in \citep{Lu10a} and the SINCO greedy code by \citet{Sche09} on randomly generated problems.} \label{tab:cpu10}}
\end{center}
\end{table}

\begin{table}[H]
\begin{center}
\begin{tabular}{r|rrrr}
Dimension & Covpath & Glasso & ASPG & SINCO\\
\hline
20&\bf0.0101&0.64&2.66&1.1827\\
50&\bf0.0491&1.91&23.2&22.0436\\
100&\bf0.0888&10.60&140.75&122.4048\\
200&\bf0.3195&61.46&681.72&451.6725\\
300&\bf0.8322&519.05&5203.46&1121.0408\\
\end{tabular}
\caption{{\small CPU time (in seconds) versus problem dimension for computing a regularization path for 50 values of the penalty $\rho$, using the path following method detailed here (Covpath), the Glasso code with warm-start (Glasso), the pathwise code (ASPG) in \citep{Lu10a} and the SINCO greedy code by \citet{Sche09}  on randomly generated problems.} \label{tab:cpu50}}
\end{center}
\end{table}

In Figure~\ref{fig:nnz}, we plot the number of nonzero coefficients (cardinality) in the inverse covariance versus penalty parameter~$\rho$, along a path of solutions to problem (\ref{eq:covsel}). We observe that the solution cardinality appears to be linear in the log of the regularization parameter. We then plot the number of conjugate gradient iterations required to compute the predictor in~\S\ref{ss:pred} versus number of nonzero coefficients in the inverse covariance matrix. We notice that the number of CG iterations decreases significantly for sparse matrices, which makes computing predictor directions faster at the sparse (i.e. interesting) end of the regularization path. Nevertheless, the complexity of corrector steps dominates the total complexity of the algorithm and there was little difference in computing time between using the scaling method detailed in \S\ref{s:algo} and using the predictor step, hence the final version of our code and the CPU time results listed here make use of scaling/warm-start exclusively, which is more robust.

\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{./figures/nnz.eps}
\caption{{\em Left:} We plot the fraction of nonzero coefficients in the inverse covariance versus penalty parameter $\rho$, along a path of solutions to problem (\ref{eq:covsel}). {\em Right:} Number of conjugate gradient iterations required to compute the predictor step versus number of nonzero coefficients in the inverse covariance matrix. \label{fig:nnz}}
\end{center}
\end{figure}

\iffalse
\begin{figure}[!h]
\begin{center}
\begin{tabular}{ccc}
\includegraphics[width=.3\textwidth]{./figures/Rates02.eps} &
\includegraphics[width=.3\textwidth]{./figures/Rates008.eps}&
\includegraphics[width=.3\textwidth]{./figures/Rates006.eps}
\end{tabular}
\caption{Three sample dependence graphs corresponding to the solution of problem (\ref{eq:covsel}) on a U.S. forward rates covariance matrix for $\rho=.02$ (left), $\rho=.008$ (center) and $\rho=.006$ (right). \label{fig:ratespath}}
\end{center}
\end{figure}
\fi

\iffalse
\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{./figures/TopicNet2.eps}
\caption{Topic network for the Science Correlated Topic Model in \cite{Blei07}. Network layout using cytoscape. Graph edge color is related to the sign of the conditional correlation (green for positive, red for negative) while edge thickness is proportional to the correlation magnitude. \label{fig:science}}
\end{center}
\end{figure}
\fi

\section{Online Covariance Selection}
\label{s:onl}

In this section, we will briefly discuss the {\em online} version of the Covariance Selection problem. This version arises if we obtain a better estimate of the covariance matrix after the problem is already solved for a set of parameter values. We will assume that the new (positive definite) covariance matrix $\hat{\Sigma}$ is the sum of the old covariance matrix $\Sigma$ and an arbitrary symmetric matrix $C$. With such a change, the `new' dual problem can be written as

\begin{equation}\label{eq:covsel-dual-onl}
\begin{array}{ll}
\mbox{minimize} &  -\log \det (U) - n \\
\mbox{subject to} & U_{ij} \leq \rho +\Sigma_{ij} +\mu C_{ij}, \quad i,j=1,\ldots,n, \\
                  & U_{ij} \geq \Sigma_{ij} +\mu C_{ij} - \rho, ,\quad i,j=1,\ldots,n,
\end{array}\end{equation}
in the variable $U\in\symm_n$, where $\rho$ is a parameter value for which the corresponding optimal solution is already calculated with the old covariance matrix $\Sigma$. The problem is parametrized with $\mu$, so that $\mu = 0$ gives the original problem whereas $\mu=1$ corresponds to the new problem.

For many applications, one would expect $C$ to be small and the optimal solution $U^*$ of the original problem to be close to the optimal solution of the new problem, say $\hat{U}^*$. Hence, regardless of the algorithm, $U^*$ should be used as an initial solution instead of solving the problem from scratch.

In the spirit of the barrier methods and the predictor-corrector method that we have devised in this chapter, we can develop a predictor-corrector algorithm to solve the online version of the problem fast as follows. We form a parametrized version of the regularized problem

\begin{equation}\label{eq:regularized-ONL}
\begin{array}{ll}
\displaystyle \min_{U\in\symm_n} & -\log \det (U) -  t\sum_{i,j=1}^n \log(\rho +\Sigma_{ij} +\mu C_{ij}
-U_{ij})\\
&    - t \sum_{i,j=1}^n \log (\rho -\Sigma_{ij} - \mu C_{ij} + U_{ij})
\end{array}\end{equation}
in the variable $U \in \symm_n$ and $t > 0$ the tradeoff level as before.
Let us define matrices  $\hat{L}, \hat{M} \in\symm_n$ as follows
\[
\hat{L}_{ij}(U,\mu) = \frac{t}{\rho+\Sigma_{ij} + \mu C_{ij}-U_{ij}} \quad \mbox{and} \quad
\hat{M}_{ij}(U,\mu) = \frac{t}{\rho-\Sigma_{ij}-\mu C_{ij}+U_{ij}}
\]
As before, optimal $\hat{L}$ and $\hat{M}$ should satisfy $ (\hat{L} -\hat{ M}) = U^{-1}$, and problem (\ref{eq:regularized-ONL}) traces a central path towards the optimal solution to problem (\ref{eq:covsel-dual-onl}) as $t$ goes to 0.

Defining
\[
\hat{H}(U,\mu) = \hat{L}(U,\mu) - \hat{M}(U,\mu) - U^{-1},
\]
we trace the curve $\hat{H}(U,\mu)=0$, the first order optimality condition for problem (\ref{eq:regularized-ONL}), from the solution for the original problem to one for the new problem as $\mu$ goes from 0 to 1. The resulting predictor-corrector algorithm is Algorithm \ref{alg:covpath-ONL}, which solves the online version efficiently.

\begin{algorithm}[ht]
\caption{Online Pathwise Covariance Selection}
\label{alg:covpath-ONL}
\begin{algorithmic} [1]
\REQUIRE $\Sigma, U^*\in\symm_m$, $\rho \in {\mbox{\bf R}}$, and $c \in {\mbox{\bf R}}^{n \times r}$.
\STATE Start with $(U_0, \mu_0)$ s.t  $\hat{H}(U_0,\mu_0) =0$, specifically, set $\mu_0=0$ and $U_0 = U^*$.
\FOR{$i=1$ to $k$}
\STATE\emph{Predictor Step}. Let $\mu_{i+1} = \mu_i + 1/k$. Compute a tangent direction by solving the linear system
\[
\frac{\partial \hat{H}}{\partial \mu}(U_i,\mu_i) + J(U_i,\mu_i) \frac{\partial U}{\partial\mu} = 0
\]
in $\partial U/\partial \mu\in\symm_n$, where $J(U_i,\mu_i)=\partial \hat{H}(U,\mu)/\partial U\in\symm_{n^2}$ is the Jacobian matrix of the function $\hat{H}(U,\mu)$.
\STATE Update $U_{i+1} = U_i + (\partial U/\partial \mu)/k$.
\STATE\emph{Corrector Step}. Solve problem (\ref{eq:regularized-ONL}) for $\mu_{i+1}$ starting at $U = U_{i+1}$.
\ENDFOR
\ENSURE Matrix $U_k$ that solves Problem (\ref{eq:covsel-dual-onl}).
\end{algorithmic}
\end{algorithm}

As for the offline version, the most demanding computation in this algorithm is the calculation of the tangent direction which can be carried out by the CG method discussed above. When carefully implemented and tuned, it produces a solution for the new problem very fast. Although one can try different values of $k$, setting $k=1$, and applying one step of the algorithm is usually enough in practice. This algorithm, and the online approach discussed in this section in general, would be especially useful and sometimes necessary for very large data sets as solving the problem from scratch is an expensive task for such problems and should be avoided whenever possible.

\section*{Acknowledgements}
The authors are grateful to two anonymous referees whose comments significantly improved the paper. The authors would also like to acknowledge support from NSF grants SES-0835550 (CDI), CMMI-0844795 (CAREER), CMMI-0968842, a Peek junior faculty fellowship, a Howard B. Wentz Jr. award and a gift from Google.

\bibliographystyle{plainnat}


\section{Introduction\label{sec:Introduction}}

Bak, Tang, and Wiesenfeld (BTW) \cite{BTW} introduced a concept
of self-organized criticality (SOC) to study dynamical systems with
spatial degree of freedom. They proposed a simple model with conservative
and deterministic relaxation rules to demonstrate the SOC phenomenon.
Manna \cite{Manna} designed another conservative SOC model in which
stochastic relaxation rules were defined. Striving to find common
features of the models and to know their basic behaviors stimulated
many numerical and theoretical studies during the past two decades.

Based on renormalization group calculations, Pietronero \textit{et
al}. \cite{Pietro} claimed that both deterministic \cite{BTW}
and stochastic models \cite{Manna} belong to the same universality
class, i.e. a small modification in the relaxation rules cannot change
universality class. Chessa \textit{et al}. \cite{Stanley} assumed
that finite size scaling (FSS) is common property of both deterministic
\cite{BTW} and stochastic \cite{Manna} models. With FSS the avalanche
size, area, lifetime, and perimeter follow power laws with cutoffs
\cite{Stanley}:

\begin{equation}
P(x)=x^{-\tau_{x}}F(x/L^{D_{x}}),\label{eq:FSS}\end{equation}

where $P(x)$ is the probability density function of $x$, $F$ is
the cutoff function, and $\tau_{x}$ and $D_{x}$ are the scaling
exponents. The set of scaling exponents $(\tau_{x},\: D_{x})$ defines
the universality class \cite{Stanley}. A SOC model is \textit{Abelian}
if a final stable configuration (see below) does not depend on the
relaxation order. The BTW model is \textit{Abelian}, however the M
model is also \textit{Abelian} \cite{Dhar} only if we consider probabilities
of many stable configurations.

Based on numerical simulations and an extended set of exponents, Ben-Hur
and Biham \cite{Hur} claimed that the BTW and M models cannot belong
to the same universality class. A precise numerical analysis of probability
density functions $P(x)$ led L\"{u}beck and Usadel \cite{Lubeck}
to the same conclusion. Essential progress to understand the discrepancy
between theoretical \cite{Pietro,Stanley} and numerical conclusions
\cite{Hur,Lubeck} has been achieved by Tebaldi \emph{et al.} \cite{Tebaldi}.
They found that avalanche size probability density functions $P(s)$
do not display FSS but show a multifractal scaling i.e. the avalanche
size exponent $\tau_{s}$ (Eq. \ref{eq:FSS}) does not apply to the
BTW model. Karmakar \emph{et al. }\cite{Karmakar_prl} proposed a
hypothesis that the presence or absence of a precise relaxation balance
between the amount released by a site and the total quantity which
the same site receives when all its neighbors relax at once determines
the appropriate universality class. Based on the precise relaxation
balance hypothesis \cite{Karmakar_prl} Karmakar and Manna \cite{Karmakar_pre}
proposed a flow chart to classify different SOC models into two universality
classes i.e. the BTW and Manna universality classes.

The probability density functions of avalanche sizes $P(s)$ in Eq.
\ref{eq:FSS} show transitions from multifractal to FSS scaling for
certain densities of disturbing sites \cite{Karmakar_prl,Cernak_2006}.
The models \cite{Karmakar_prl,Cernak_2006} are stochastic and \textit{non-Abelian}
with unbalanced relaxation rules \cite{Karmakar_prl}. In this study,
I focus on verifying an existence of such transitions for the deterministic
and \textit{Abelian} model \cite{cer_2002} (In the orginal paper
\cite{cer_2002} the model was incorrectly clasified as non-\textit{Abelian})
with unbalanced relaxation rules. The model \cite{cer_2002} displays
an anomalous increase of the avalanche size area exponents $\tau_{a}$
(Eq. \ref{eq:FSS}) for densities near $c=0.01$ and thresholds $E_{c}^{II}\geq16$.
However, the cause of this anomalous behavior is not well understood.
I assumed that the transition from multifractal to FSS scaling could
take place for density $c<0.01$ and threshold $E_{c}^{II}\geq16$,
because relaxation rules change character from balanced ($c=0.0$)
to unbalanced ($c>0.0$). To characterize avalanche size scaling I
investigated avalanche wave dynamics \cite{Menech,Stella}, Hurst
exponents \cite{Menech}, avalanche structures \cite{Hur} and avalanche
size moments \cite{Menech}.

The paper is organized as follows. In Sec. \ref{sec:model} I repeat
a definition of the inhomogeneous sand pile model \cite{cer_2002}.
In Sec. \ref{sec:Results} I determine autocorrelations and fluctuations
of avalanche size waves, avalanche structures and avalanche size moments
for several densities $0.0\leq c$$\leq1.0$ and thresholds $8\leq E_{c}^{II}\leq32$.
Sec. \ref{sec:Discussion} is devoted to a discussion which is followed
by conclusions in Sec. \ref{sec:Conclusion}.

\section{\label{sec:model} An Abelian deterministic and conservative self
organized criticality model}

The inhomogeneous sand pile model \cite{cer_2002} is defined on
a two dimensional lattice of size $L\times L$. Each site $\mathbf{i}$
has assigned variables $E(\mathbf{i})$ and $E_{c}(\mathbf{i})$.
The variable $E(\mathbf{i})$ is dynamical and it represents a physical
quantity such as energy, grain density, and etc. The threshold $E_{c}(\mathbf{i})$
is a static value at site $\mathbf{i}$ which is defined only once
during initialization of simulations. The threshold $E_{c}(\mathbf{i})$
has two values \cite{cer_2002}:

\begin{eqnarray}
E_{c}(\mathbf{i}) & = & \begin{cases}
E_{c}^{I}=2d\\
E_{c}^{II}=2dk, & k=2,3,4,\ldots,\end{cases}\end{eqnarray}

where $d$ is a dimension and $k$ is a natural number. The model
has two parameters namely the density $c=n/L^{2}$ and threshold $E_{c}^{II}$
where $n$ is a number of sites with the threshold $E_{c}(\mathbf{i})=E_{c}^{II}$,
remaining $L^{2}-n$ sites have the threshold $E_{c}^{I}=4$. During
initializations of simulations, $n$ sites with thresholds $E_{c}(\mathbf{i})=E_{c}^{II}$
were picked out randomly and all remaining sites had the threshold
$E_{c}^{II}=4$, thus a set of the thresholds $\left\{ E_{c}(\mathbf{i})\right\} $
represents a quenched disorder. A stable configuration is defined
by a condition $E(\mathbf{i})<E_{c}(\mathbf{i})$ for each site $\mathbf{i}$.
Let us assume that from a stable configuration we iteratively select
$\mathbf{i}$ at random and increase $E(\mathbf{i})$$\rightarrow E(\mathbf{i})+1$.
If an unstable configuration is reached i.e. $E(\mathbf{i})\geq E_{c}(\mathbf{i})$
then a relaxation starts. The relaxation rules are conservative and
deterministic \cite{cer_2002}:

\begin{equation}
E(\mathbf{i})\rightarrow E(\mathbf{i})-\sum_{e}\triangle E(\mathbf{e}),\label{eq:r1}\end{equation}

\begin{equation}
E(\mathbf{i}+\mathbf{e})\rightarrow E(\mathbf{i}+\mathbf{e})+\triangle E(\mathbf{e}),\label{eq:r2}\end{equation}

\begin{equation}
\sum_{e}\triangle E(\mathbf{e})=E_{c}(\mathbf{i}),\label{eq:r3}\end{equation}

where $\mathbf{e}$ is a set of vectors from the site $\mathbf{i}$
to its neighbors. The relaxation rules (Eqs. \ref{eq:r1}-\ref{eq:r3})
are repeated until the site $\mathbf{i}$ becomes stable. If the neighbors
of the site $\mathbf{i}$ become unstable then avalanche can run on.
All unstable sites belong to the avalanche. The relaxations given
by Eqs. \ref{eq:r1}-\ref{eq:r3} are repeated until a stable configuration
is reached, i.e. $E(\mathbf{i})<E_{c}(\mathbf{i})$ for all sites
$\mathbf{i}$. Stable and unstable configurations are repeated many
times. A total number of relaxations during one avalanche is an avalanche
size $s.$

\section{\label{sec:Results}Numerical results}

Numerical simulations were carried out on two dimensional lattices
$L\times L$ where the linear lattice size $L$ was $L=128,\:256,\:512,\:1024,\:2048,$
and $4096$. A density $c$ and thresholds $E_{c}^{I}=4$, $E_{c}^{II}=8,\:16$
and $32$ were chosen based on the previous results \cite{cer_2002}
to cover a parameter space in which interesting behaviors were expected
(Sec. \ref{sec:Introduction}). For example, near the density $c=0.01$
an anomalous increase of the avalanche area scaling exponent $\tau_{a}$
(Eq. \ref{eq:FSS}) has been observed \cite{cer_2002}. Near densities
$c=0.0$ and $1.0$ local relaxation rules change character from balanced
($c=0.0$ and $1.0$) to unbalanced ($c>0.0$ and $c<1.0$) \cite{Karmakar_prl,Karmakar_pre},
thus a transition from multifractal to finite size scaling could take
place in the intervals $c>0.0$ and $c<1.0$. Considering these assumptions,
I have selected the density $c$ as follows: $c=a$ (surroundings
of $c=0.0$) or $c=1.0-a$ (surroundings of $c=1.0$) where $a=0,\:0.001,\:0.002,\:0.004,\;0.008,\;0.01,\:0.02,\:0.04,$
and $0.08$. In addition, to cover the whole interval $0.0<c<1.0$,
I added the sample concentrations $c=l/10$, where $l=1,\:2,\ldots,\;9$.
I have recorded about $10^{6}$ avalanches after initializations of
simulations in which an avalanche dynamics has to reach the SOC state
\cite{BTW}. To qualify a reproducibility of the results all numerical
simulations were repeated once for each lattice size $L\times L$,
concentration $0.0\leq c$$\leq1.0$ and threshold $E_{c}^{II}$.
A comparison of these data sets showed that the results are well reproducible.

A possibility to decompose an avalanche into waves \cite{Ivash}
is a significant advantage of computer models. Because avalanche wave
dynamics \cite{Menech,Stella} can provide valuable initial information
about the character of an SOC model. An avalanche of size $s$ is
decomposed into $m$ waves with size $s_{k}$, where $s=\sum_{k=1}^{m}s_{k}$.
A time sequence of avalanche waves $s_{k}$ is used to determine the
autocorrelation function \cite{Menech,Stella}

\begin{equation}
C(t,\: L)=\frac{\langle s_{k+t}s_{k}\rangle_{L}-\langle s_{k}\rangle_{L}^{2}}{\langle s_{k}^{2}\rangle_{L}-\langle s_{k}\rangle_{L}^{2}},\end{equation}

where time is $t=1,\:2,\ldots,$ and the time averages are taken over
$5\times10^{6}$ waves. Autocorrelations $C(t,\: L,\: c)$ have been
analyzed for the time $1\leq t\leq1000$, lattice sizes $128\leq L\leq4096$,
selected concentrations $0.0\leq c\leq1.0$ and thresholds $E_{c}^{I}=4,$
$E_{c}^{II}=8,\:16$, and $32$ (see above). The autocorrelations
$C(t,\: L=4096,\: c)$ for the biggest lattice size $L=4096$ are
shown in Fig. \ref{fig:Autocorrelation}. I have observed that for
the density $c=1.0$, the autocorrelations $C(t,\: L=4096,\: c=1.0)$
agree within experimental error with autocorrelations of the BTW model
\cite{Menech} ($C(t,\: L=4096,\: c=0.0)$) . I note that the autocorrelations
$C(t,\: L=4096,\: c=0.0)$ are not shown in Fig. \ref{fig:Autocorrelation}.
I have approximated the autocorrelations $C(t,\: L,\: c=0,\:1.0)$
by a simple function $C(t,L,c=0,\:1.0)\sim\exp(-\alpha t)$ where
$\alpha$ is a decay rate \cite{cer_2008}. For more general conditions,
densities $0.0<c<1.0$ (Fig. \ref{fig:Autocorrelation}), the autocorrelations
$C(t,\: L,\: c)$ are more complex functions than for specific densities
$c=0.0$ and $1.0$. I have found that with increasing time $t$,
the autocorrelations $C(t,\: L,\: c)$ are decreasing functions. An
unexpected finding is the existence of oscillating components of autocorrelations.
For all densities $0.0<c<1.0$ (Fig. \ref{fig:Autocorrelation}(a))
and the threshold $E_{c}^{II}=8$ their periods are approximately
constant. Amplitudes of oscillating components decrease with increasing
density $c$ and time $t$. At the given time $t$ the autocorrelations
$C(t,\: L,\: c)$ increase if a density $c$ increases, i.e. if $c_{2}\geq c_{1}$
then $C(t,\: L,\: c_{1})\geq C(t,\: L,\: c_{2})$. Near densities
$c=0.0$ and $1.0$, the oscillating parts of $C(t,\: L,\: c)$ disappear.
I have observed more complex behaviors (Fig. \ref{fig:Autocorrelation}
(b) and (c)) for thresholds $E_{c}^{II}\geq16$ than for the threshold
$E_{c}^{II}=8$ ((Fig. \ref{fig:Autocorrelation} (a)). The oscillating
components of $C(t,\: L,\: c)$ (Fig. \ref{fig:Autocorrelation}(b))
have longer periods for densities $c<0.08$ and threshold $E_{c}^{II}=16$
than for the threshold $E_{c}^{II}=8$. However, odd periods were
split for densities $c>0.08$. The same effect take place for the
threshold $E_{c}^{II}=32$, but a critical density is higher $c\doteq0.40$
(Fig. \ref{fig:Autocorrelation}(c)). After splitting the oscillating
components, for thresholds $E_{c}^{II}=16$ and $32$, their new periods
were approximately equal to the period which has been found for the
threshold $E_{c}^{II}=8$.

\begin{figure*}
\includegraphics[width=6cm]{fig1a}\includegraphics[width=6cm]{fig1b}\includegraphics[width=6cm]{fig1c}

\caption{\label{fig:Autocorrelation}Autocorrelations $C(t,\: L,\: c)$ for
the linear lattice size $L=4096$, for densities $0.001\leq c\leq1.0$
and for thresholds $E_{c}^{I}=4$, (a) $E_{c}^{II}=8$, (b) $E_{c}^{II}=16$,
and (c) $E_{c}^{II}=32$. The autocorrelations $C(t,L,c=0)$ are not
shown.}

\end{figure*}

Stochastic processes are often characterized by Hurst exponents \cite{Mandelbrot}.
To determine the Hurst exponent the fluctuation $F(t,\: L)$ \cite{Menech}:

\begin{equation}
F(t,\: L)=\left[\langle\Delta y(t)^{2}\rangle_{L}-\langle\Delta y(t)\rangle_{L}^{2}\right]^{1/2}\end{equation}

is used where $y(t)=\sum_{k=1}^{t}s_{k}$ and $\Delta y(t)=y(k+t)-y(k)$.
If a fluctuation $F(t,\: L)$ scales with the time $t$ as $F(t,\: L\rightarrow\infty)\sim t^{H}$
then $H$ is the Hurst exponent.

\begin{figure}
\includegraphics[width=7cm]{fig2}

\caption{\label{fig:Fluct.}(Color online) Fluctuations $F(t,\: L=4096)$ for
densities $c=0.000,\:0.001,\:040$ and $0.999$ and the threshold
$E_{c}^{II}=32$.}

\end{figure}

I have determined fluctuations and the corresponding Hurst exponents
for the lattice size $L=4096$, selected concentrations $c$ (see
above) and thresholds $E_{c}^{I}=4,$ $E_{c}^{II}=8,\:16$, and $32$.
For all these parameters fluctuations show two scaling regions $1<t_{1}<100$
and $1000<t_{2}<10000$. The fluctuations $F(t,\: L)$, for densities
$c=0.000,\:0.001,\:040$ and $0.999$ and threshold $E_{c}^{II}=32$,
are shown in Fig. \ref{fig:Fluct.} to demonstrate the existence of
two scaling intervals. The Hurst exponents $H_{1}(c)$ and $H_{2}(c)$
as functions of density $c$ and threshold $E_{C}^{II}$ are shown
for all parameters (densities $0.0\leq c\leq1.0$ and thresholds $8\leq E_{c}^{II}\leq32$)
in Fig. \ref{fig:Hurst}. I have observed that the exponents $H_{1}(c)$
and $H_{2}(c)$ depend on the parameters (density $c$ and threshold
$E_{C}^{II}$) in a nontrivial manner (Fig. \ref{fig:Hurst}). For
densities $0.0\leq c\leq1.0$ and thresholds $8\leq E\leq32$ functions
$H_{1}(c)$ are bounded by the interval $0.68<H_{1}(c)<0.81$. Similarly,
the functions $H_{2}(c)$ are limited by the interval $0.44<H_{2}(c)\leq0.56$.
The exponents $H_{1}(c)\doteq0.80$ and $H_{2}(c)\doteq0.50$ are
approximately constant for densities $c>0.50$. I have observed anomalous
decreases of functions $H_{1,\,2}(c)$ near low densities $0.0<c\leq0.01$
(Fig. \ref{fig:Hurst}). In addition, functions of $H_{1\,,2}(c)$
have a decreasing tendency if the second thresholds $E_{c}^{II}$
increase. Finally, the functions $H_{1,2}(c)$ are not symmetric around
the density $c=1/2$, i.e. $H_{1}(0.5-a)\neq H_{1}(0.5+a)$ and $H_{2}(0.5-a)\neq H_{2}(0.5+a)$
for $0.0<a<0.5$ except the specific densities $c=0.0$ and $c=1.0$,
where $H_{1}(0.0)\doteq H_{1}(1.0)$ and $H_{2}(0.0)\doteq H_{2}(1.0)$
within experimental errors.

\begin{figure*}
\includegraphics[width=6cm]{fig3a}\includegraphics[width=6cm]{fig3b}\includegraphics[width=6cm]{fig3c}

\caption{\label{fig:Hurst}Hurst exponents $H_{1}(c)$and $H_{2}(c)$ as functions
of a densities $c$ and thresholds: $E_{c}^{I}=4$, (a) $E_{c}^{II}=8$,
(b) $E_{c}^{II}=16$, and (c) $E_{c}^{II}=32$ for the lattice size
$4096\times4096$. The Hurst exponents at given density $c$, $H_{1}(c)$
and $H_{2}(c)$ were approximated using the power laws $F(t,\: L)\sim t^{H_{1}(c)}$
and $F(t,\: L)\sim t^{H_{2}(c)}$ in the intervals $t=1-100$ and
$t=10^{3}-10^{4}$. }

\end{figure*}

Ben-Hur and Biham \cite{Hur} proposed to use avalanche structures
to demonstrate a difference between BTW \cite{BTW} and M \cite{Manna}
models. An avalanche structure consists of clusters of sites with
equal numbers of relaxations. The BTW model displays rigorous shell-like
structures \cite{Hur,Karmakar_prl} and the M model displays disordered
structures \cite{Hur} with inner holes \cite{Karmakar_prl}. I
have analyzed several avalanche structures (Fig. \ref{fig:avalanche})
of the inhomogeneous sand pile model \cite{cer_2002} to compare
them with known structures \cite{Hur,Karmakar_prl}.

\begin{figure*}
\includegraphics[width=4cm,angle=90]{fig4a}(a) \includegraphics[width=4cm]{fig4b}(b)
\includegraphics[width=4cm]{fig4c}(c)

\includegraphics[width=4cm]{fig4d}(d) \includegraphics[width=4cm]{fig4e}(e)
\includegraphics[width=4cm]{fig4f}(f)

\includegraphics[width=4cm]{fig4g}(g) \includegraphics[width=4cm]{fig4h}(h)
\includegraphics[width=4cm]{fig4i}(i)

\caption{\label{fig:avalanche}Avalanche structures on two dimensional lattice
$128\times128$ for parameters $E_{c}^{I}=4$, (a) $E_{C}^{II}=8$,
$c=0.02$, (b) $E_{C}^{II}=8$, $c=0.5$, (c) $E_{C}^{II}=8$, $c=0.98$,
(d) $E_{C}^{II}=16$, $c=0.02$, (e) $E_{C}^{II}=16$, $c=0.5$, (f)
$E_{C}^{II}=16$, $c=0.98$, (g) $E_{C}^{II}=32$, $c=0.02$, (h)
$E_{C}^{II}=32$, $c=0.5$, and (i) $E_{C}^{II}=32$, $c=0.98$. Lattice
sites with the same numbers of relaxations are shown by the same color
(rainbow pseudo-color coding).}

\end{figure*}

I have observed the avalanche structures which resemble the shell-like
structure for densities $c=0.02$ (Fig. \ref{fig:avalanche}(a), (d),
and (g)) and $c=0.98$ (Fig. \ref{fig:avalanche} (c), (f), and (i)).
However, these structures are not exactly shell-like. A clear visible
difference is the existence of holes in an avalanche, for example
see Figs. \ref{fig:avalanche}(a), (b), and (d). The sizes of these
holes vary from one site (obviously a site with $E_{c}^{II}>E_{c}^{I}$)
to several sites. Mainly, for low densities ($c=0.02)$ an existence
of holes is clearly demonstrated in Figs. \ref{fig:avalanche}(a),
(d), and (g) where the sites with the threshold $E_{c}^{II}$ can
absorb and relax more energy than surrounding sites with $E_{c}^{I}$.
If the sites ($E_{c}^{II}$) absorb energy then they are well identified
as small holes inside the avalanche structure (Figs. \ref{fig:avalanche}(a),
(d), and (g)). If the sites ($E_{c}^{II}$) release more energy than
their neighbors (with threshold $E_{c}^{I}$) then the sites ($E_{c}^{II}$)
involve instabilities of many sites within a certain distance. These
sites must relax to be stable (Fig. \ref{fig:avalanche} (d)). At
high density $c=0.98$, the sites with the lower threshold $E_{c}^{I}$
are considered for disturbing sites. A site with threshold $E_{c}^{I}$
can receive more energy from neighbors than a critical amount of the
site (threshold $E_{c}^{I}$). Then the site ($E_{c}^{I}$) must relax
more times than neighbors (sites with the threshold $E_{c}^{II}$)
to be stable. The disturbing sites are shown as isolated sites in
Figs. \ref{fig:avalanche}(c), (f), and (i). The effects of disturbing
sites $E_{c}^{II}$ and $E_{c}^{I}$ differs, for the small density
$c=0.02$, the disturbing sites $E_{c}^{II}$ can absorb and relax
more energy as their neighbors. However, for high density $c=0.98$,
the disturbing sites $E_{c}^{I}$ can only do more relaxations than
their neighbors sites.

I have found new avalanche structures which resemble neither shell-like
(the BTW mode) nor disordered (the M model) \cite{Hur,Karmakar_prl}
for density $c=0.50$ and thresholds $8\leq E_{c}^{II}\leq32$ Figs.
\ref{fig:avalanche}(b), (e), and (h). Their typical feature is the
existence of complex clusters in avalanche which more resemble percolation
clusters.

The model (Sec. \ref{sec:model}) displays shell-like avalanche structures
as well as the BTW model \cite{Hur,Karmakar_prl} only for the specific
densities $c=0.0$ and $c=1.0$.

\begin{figure*}
\includegraphics[width=6cm]{fig5a}\includegraphics[width=6cm]{fig5b}\includegraphics[width=6cm]{fig5c}

\caption{\label{fig:scal}Scaling of avalanche size moments $\langle s^{q}\rangle$
versus the lattice size $128\leq L\leq4096$. The exponents $q$ are
$q=1.0,\:2.0,\:3.0,\:3.5$ and $3.95$ from bottom to top. The model
parameters are $E_{c}^{I}=4$, $E_{c}^{II}=32$, (a) $c=0.008$, (b)
$c=0.40$ and (c) $c=0.992$.}

\end{figure*}

Sometimes we cannot decompose an avalanche into waves, obviously if
we study real systems, then avalanche moments \cite{Menech} are
useful. A property $x$ in FSS obeys scaling given by Eq. \ref{eq:FSS}.
The moments $q$ are \cite{Menech}:

\begin{equation}
\langle x^{q}\rangle=\int_{_{0}}^{x_{max}}x^{q}P(x,L)dx\sim L^{\sigma_{x}(q)}\label{eq:moment}\end{equation}
 where $\sigma_{x}(q)=(q+1-\tau_{x})D_{x}$ and $x_{max}\sim L^{D_{x}}$.
I have determined only avalanche size moments $\langle s^{q}\rangle$
versus the lattice size $L$ which are shown in Fig. \ref{fig:scal}
for densities $c=0.008$, $c=0.40$ and $c=0.992$ and for thresholds
$E_{c}^{I}=4$ and $E_{c}^{II}=32$. The moments $\langle s^{q}\rangle$
scale with the lattice size $L$ as well as $\langle s^{q}\rangle\sim L^{\sigma_{x}(q)}$
(Eq. \ref{eq:moment}), thus a basic requirement is met to determine
$\sigma_{s}(q)$.

\begin{figure*}
\includegraphics[width=6cm]{fig6a}\includegraphics[width=6cm]{fig6b}\includegraphics[width=6cm]{fig6c}

\caption{\label{fig:dsigma}Plots $\partial\sigma_{s}(q)/\partial q$ versus
exponent $q$ for the lattice size $4096\times4096$, concentrations
$0.0<c\leq1.0$ and thresholds: $E_{c}^{I}=4,$ (a) $E_{c}^{II}=8$,
(b) $E_{c}^{II}=16$, and (c) $E_{c}^{II}=32$.}

\end{figure*}

Using the functions $\sigma_{s}(q)$ I determined the plots $\partial\sigma_{s}(q)/\partial q$
versus the exponent $q$ which are shown in Fig. \ref{fig:dsigma}
for densities $0.0<c\leq1.0$ and thresholds $4<E_{c}^{II}\leq32$.
I have observed that the functions $\partial\sigma_{s}(q)/\partial q$
are increasing if exponents $q$ increase (Fig. \ref{fig:dsigma})
for exponents $q>1.0$, densities $0.0<c<1.0$ and thresholds $8\leq E_{c}^{II}\leq32$.
Surface cuts $\partial\sigma_{s}(q)/\partial q\:\mid_{q=1.0}$ and
$\partial\sigma_{s}(q)/\partial q\:\mid_{q=4.0}$, for exponents $q=1.0$
and $q=4.0$, as functions of density $c$ are shown in Fig. \ref{fig:dq}
to demonstrate this increasing tendency. I have found that $\partial\sigma_{s}(q)/\partial q\:\mid_{q=4.0}>\partial\sigma_{s}(q)/\partial q\:\mid_{q=1.0}$,
$\partial\sigma_{s}(q)/\partial q\:\mid_{q=1.0}\neq const.$ and $\partial\sigma_{s}(q)/\partial q\:\mid_{q=4.0}\neq const.$
(Fig. \ref{fig:dq}) for densities $0.0<c<1.0$ and thresholds $8\leq E_{c}^{II}\leq32$.
This implies that functions $\partial\sigma_{s}(q)/\partial q$ differ
from the function $\partial\sigma_{s}(q)/\partial q$ of the BTW model.
However, for the specific parameters $c=0.0$, $c=1.0$ and $8\leq E_{c}^{II}\leq32$
relaxation rules are precisely balances and the functions $\partial\sigma_{s}(q)/\partial q$
versus $q$ ($q\geq1.0$) are identical within experimental errors
with the function $\partial\sigma_{s}(q)/\partial q$ of the BTW model
\cite{Menech,Karmakar_prl}.

\begin{figure*}
\includegraphics[width=6cm]{fig7a}\includegraphics[width=6cm]{fig7b}\includegraphics[width=6cm]{fig7c}

\caption{\label{fig:dq}The plots $\partial\sigma_{s}(q)/\partial q\mid_{q=1}$
(errors $\pm0.01$) and $\partial\sigma_{s}(q)/\partial q\mid_{q=4}$(errors
$\pm0.03$) versus density $c$ for the linear lattice size $L=4096$
and thresholds $E_{c}^{I}=4$, (a) $E_{c}^{II}=8$, (b) $E_{c}^{II}=16$,
and (c) $E_{c}^{II}=32$.}

\end{figure*}

\section{\label{sec:Discussion}Discussion}

I have found that autocorrelations $C(t,\: L,\: c)$ (Fig. \ref{fig:Autocorrelation})
are more complex functions than an autocorrelation of the BTW model
\cite{Menech,Karmakar_prl}. The autocorrelations exhibit oscillating
components (Fig. \ref{fig:Autocorrelation}) which periods and amplitudes
depend on both densities $0.0<c<1.0$ and thresholds $8\leq E_{c}^{II}\leq32$.
The oscillating components are probably caused by a periodicity in
an avalanche wave sequence. I assume that the periodicity could be
a consequence of an excessive energy storing and release in sites
with the thresholds $E_{c}^{II}$, apparently when the sites have
low concentration $c<0.5$. In such conditions, relaxations of these
sites trigger relaxations of surrounding sites, i.e. all surrounding
sites within a certain distance from a disturbing site have to relax
\cite{cer_2002}. This hypothesis could be supported by finding that
for the same time $t$ amplitudes of oscillating components are decreasing
if densities $c$ increase and oscillations disappear near the density
$c=1.0$ (Fig. \ref{fig:Autocorrelation}). The periods were longer
for low densities $c<0.4$ and thresholds $E_{c}^{II}\geq16$ than
for the threshold $E_{c}^{II}=8$. This could be connected with the
stronger effect of disturbing sites $E_{c}^{II}\geq16$ which can
store and release much more energy than disturbing sites $E_{c}^{II}=8$.
However, a nontrivial dependence of periods on thresholds $E_{c}^{II}\geq8$
and densities $c$ (Fig. \ref{fig:Autocorrelation}) and the cause
of period splitting for thresholds $E_{c}^{II}\geq16$ and critical
densities $c$ (Fig. \ref{fig:Autocorrelation} (b) and (c)) are not
understood. For specific densities $c=0.0$ and $c=1.0$, the autocorrelations
$C(t,\: L,\: c=0.0)$ and $C(t,\: L,\: c=1.0)$ agree well with autocorrelation
of the BTW model \cite{Karmakar_prl,Menech}. I have found correlated
avalanche waves under more general conditions in which the relaxation
rules are unbalanced \cite{Karmakar_prl} for densities $0.0<c<1.0$
and thresholds $8\leq E_{c}^{II}\leq32$. This is completely opposite
to the result the hypothesis predicted \cite{Karmakar_prl,Karmakar_pre}.
I think that the hypothesis about a precise relaxation balance \cite{Karmakar_prl,Karmakar_pre}
is valid only for the specific densities $c=0.0$ and $c=1.0$ and
thresholds $8\leq E_{c}^{II}\leq32$.

Two scaling intervals of fluctuations $F(t,\: L=4096)$ (Fig. \ref{fig:Hurst})
support correlated avalanche waves \cite{Menech} for densities $0.0\leq c\leq1.0$
and thresholds $8<E_{c}^{II}\leq32$. The fluctuations $F(t,\: L=4096)$
agree well with a fluctuation of the BTW model only for the densities
$c=0.0$ and $c=1.0$ \cite{Menech,Karmakar_prl} when relaxation
rules are precisely balanced \cite{Karmakar_prl}. For all other
parameters, densities $0.0<c<1.0$ and thresholds $8\leq E_{c}^{II}\leq32$,
relaxation rules are unbalanced and the hypothesis \cite{Karmakar_prl,Karmakar_pre}
predicts a single scaling region with the Hurst exponent $H=1/2$.
However, I have not found single scaling regions of $F(t,\: L=4096)$.
So the fluctuations $F(t,\: L=4096)$ contradict the hypothesis of
precise relaxation balance \cite{Karmakar_prl,Karmakar_pre}. Asymmetries
of functions $H_{1,2}(c)$ to permutations of densities $c$ (Fig.
\ref{fig:Hurst}) could be a consequence of different local effects
of disturbing sites $E_{c}^{II}$ near density $c=0.0$ and disturbing
sites $E_{c}^{I}$ near density $c=1.0$. The Hurst exponents $H_{1}(c)$
are limited by the interval $0.68<H_{1}(c)<0.8$ near the density
$c=0.0$ thus avalanche waves are less correlated than in the BTW
model ($H_{1}=0.8$) and they are more correlated than in the M model
($H=0.5$). The Hursts exponents $H_{2}(c)$ are limited by the interval
$0.44<H_{2}(c)\leq0.56$ which indicate that local perturbation effects
can change a long-term persistence (antipersistence) \cite{Mandelbrot}.
The changes of Hurst exponents $H_{1,2}(c)$ with density $c$ and
threshold $E_{c}^{II}$ demonstrate that local perturbation effects
could change a global wave dynamics.

I assume that avalanche wave dynamics (autocorrelations and fluctuations)
on a finite size lattices $L\times L$, for $L>L_{c}$ where $L_{c}$
is a critical length, can provide basic information about correlated
(the BTW model) or uncorrelated (the M model) nature of waves in avalanches
not only for the finite size $L$ but also for the size $L$ which
goes to infinity. I assume that $L=4096$ is greater than $L_{c}$.
Then conclusions regarding an avalanche wave dynamics for the finite
lattice size $L=4096$ could be extended for infinite systems.

A comparison of avalanche structures, for densities $0.0<c<1.0$ and
thresholds $8\leq E_{c}^{II}\leq32$, shows that the avalanche structures
of the model (Sec. \ref{sec:model}) are more disordered than shell-like
structures of the BTW \cite{Hur,Karmakar_prl} model but they are
more ordered than structures of the M model \cite{Hur,Karmakar_prl}.
Only for the specific densities $c=0.0$ and $c=1.0$, the avalanche
structures are exactly shell-like as well as in the BTW model \cite{Hur,Karmakar_prl}.
I assume that connection between avalanche structures and autocorrelations
near the density $c=0.5$ are more weak for the model (Sec. \ref{sec:model})
than for the BTW or M models \cite{Hur,Karmakar_prl}. Because avalanche
structures are more disordered (Fig. \ref{fig:avalanche}) than structures
of the BTW model and more ordered than structures of the M model,
however avalanche waves are correlated as in Fig. \ref{fig:Autocorrelation}.

A hypothesis about a precise relaxation balance \cite{Karmakar_prl}
for unbalanced relaxation rules predicts FSS where $\partial\sigma_{s}(q)/\partial q=const.$
for all exponents $q>1.0$. In such case, an expectation $\partial\sigma_{s}(q)/\partial q\:\mid_{q=4}\doteq\partial\sigma_{s}(q)/\partial q\:\mid_{q=1}$
is correct. However, avalanche size moments do not support this expectation,
because I have found that $\partial\sigma_{s}(q)/\partial q\:\mid_{q=4}>\partial\sigma_{s}(q)/\partial q\:\mid_{q=1}$
and functions $\partial\sigma_{s}(q)/\partial q\:\mid_{q=4}$ and
$\partial\sigma_{s}(q)/\partial q\:\mid_{q=1}$ (Fig. \ref{fig:dq})
depend on a density $c$ for all densities $0.0<c<1.0$ and thresholds
$8\leq E_{c}^{II}\leq32$. This is a reason why functions $\partial\sigma_{s}(q)/\partial q$
of the model (Sec. \ref{sec:model}) cannot be identical with the
function $\partial\sigma_{s}(q)/\partial q$ of the BTW model \cite{Karmakar_prl,Manna}
($c=0.0$ and $1.0$) for densities $0.0<c<1.0$. Although, I conclude
that avalanche waves are correlated in avalanches and avalanche sizes
scale as a multifractal for all investigated parameters.

For specific densities $c=0.0$ and $1.0$, the basic assumptions
$H_{i}-H_{i}^{'}=0$ of the precise relaxation balance hypothesis
\cite{Karmakar_prl} are correct. However, all results (Sec. \ref{sec:Results})
show a multifractal scaling of avalanche sizes not only for the specific
conditions but also for the more general conditions $0.0<c<1.0$ and
$8\leq E_{c}^{II}\leq32$ in which $|H_{i}-H_{i}^{'}|=4n$, $0\leq n\leq7$
where $n$ is a natural number. Thus I conclude that the hypothesis
about precise relaxation balance \cite{Karmakar_prl} is valid only
for the specific parameters $c=0.0$ and $1.0$ and $E_{c}^{II}>4$.

I have not observed a transition from multifractal scaling to FSS
of avalanche sizes which has been expected for low densities near
$c=0.0$ (Sec. \ref{sec:Introduction}). However, the autocorrelations,
Hurst exponents and avalanche size moments support the previous conclusions
\cite{cer_2002,cer_2008,Cernak_2006} that multifractal scaling is
very sensitive to local perturbations for densities near $c=0.0$.

Does the model belong to the BTW class? The answer is not uniform.
The model shows common features with the BTW model for example, correlated
waves in avalanches and multifractal scaling of avalanche sizes. However,
I have demonstrated that the autocorrelations (Fig. \ref{fig:Autocorrelation})
are complex functions, Hurst exponents are functions of densities
$c$ (Fig. \ref{fig:Hurst}) and holes can be found in avalanches
while all these features are not typical for the BTW model. A possible
difference between the inhomogeneous sand pile model \cite{cer_2002}
and the BTW model \cite{BTW} is supported by functions $\partial\sigma_{s}(q)/\partial q$
(Figs. \ref{fig:dsigma} and \ref{fig:dq}) which are not identical
with the function $\partial\sigma_{s}(q)/\partial q$ of the BTW model
except the specific densities $c=0.0$ and $1.0$.

\section{\label{sec:Conclusion}Conclusion}

Applying the classification scheme \cite{Karmakar_pre} on the inhomogeneous
sandpile model model (Sec. \ref{sec:model}) places the model in the
M universality class. However, I have demonstrated (Sec. \ref{sec:Results})
that the model belongs neither in the M universality class nor in
the BTW universality class (Sec. \ref{sec:Discussion}). I assume
that it belongs in a multifractal universality class \cite{Tebaldi}
which is more general than the BTW class \cite{cer_2008}. Based
on the wave autocorrelations, fluctuations, avalanche structures and
avalanche size moments, I conclude that an avalanche wave dynamics
and avalanche size scaling depend on local relaxation details. In
addition, a hypothesis about precise relaxation balance \cite{Karmakar_prl,Karmakar_pre}
could be a specific case of a more general rule. The reason why a
multifractal scaling is very sensitive to local perturbations is not
well understood.

\

\begin{acknowledgments}
The author thanks A. Read for his comments to the manuscript. Computer
simulations were carried out in the projects NorduGrid and KnowARC.
This work was supported by Slovak Research and Development Agency
under contact No. RP EU-0006-06.
\end{acknowledgments}