text:
\subsection{Notations and Definitions}
We use both element-wise and specialized tensor algebra
notation~\cite{kolda2009tensor}.
Vectors are denoted with bold lowercase Roman letters (e.g., $\vcr{v}$), matrices are denoted with bold uppercase Roman letters (e.g., $\mat{M}$), and tensors are denoted with bold calligraphic fonts (e.g., $\tsr{T}$).
An order $N$ tensor corresponds to an $N$-dimensional array.
Elements of vectors, matrices, and tensors are denotes in parentheses, e.g., $\vcr{v}(i)$ for a vector $\vcr{v}$, $\mat{M}(i,j)$ for a matrix $\mat{M}$, and $\tsr{T}(i,j,k,l)$ for an order 4 tensor $\tsr{T}$.
The $i$th column of $\mat{M}$ is denoted by $\mat{M}(:,i)$. Parenthesized superscripts are used to label different vectors, matrices and tensors (e.g. $\tsr{T}^{(1)}$ and $\tsr{T}^{(2)}$ are unrelated tensors).

The pseudo-inverse of matrix $\mat{A}$ is denoted with $\mat{A}^\dagger$. The Hadamard product of two matrices is denoted with $*$. The outer product of two or more vectors is denoted with $\circ$. The Kronecker product of two vectors/matrices is denoted with $\otimes$.
For matrices $\mat{A}\in \mathbb{R}^{I\times K}$ and $\mat{B}\in \mathbb{R}^{J\times K}$, their Khatri-Rao product resulting in a matrix of size $(IJ)\times K$ defined by
$
   \mat{A}\odot \mat{B} = [\vcr{a}_1\otimes \vcr{b}_1,\ldots, \vcr{a}_K\otimes \vcr{b}_K] .
$
The mode-$n$ TTM of an order $N$ tensor $\tsr{T} \in \mathbb{R}^{s_1\times \cdots \times s_N}$ with a matrix $ \textbf{A}\in \mathbb{R}^{J\times s_n}$ is denoted by $\tsr{T}\times_n \mat{A}$, whose output size is $s_1\times\cdots\times s_{n-1}\times J\times s_{n+1}\times\cdots\times s_N$.
Matricization is the process of unfolding a tensor into a matrix. The mode-$n$ matricized version of $\tsr{T}$ is denoted by $\textbf{T}_{(n)}\in \mathbb{R}^{s_n\times K}$ where $K=\prod_{m=1,m\neq n}^N s_m$.
We generalize this notation to define the unfoldings of a tensor $\tsr{T}$ with dimensions $s_1 \times \cdots \times s_N$ into an order $M+1$ tensor, $\tsr{T}_{(i_1,\ldots,i_M)}\in \mathbb{R}^{s_{i_1} \times \cdots \times s_{i_M}\times K}$, where $K=\prod_{j\in \{1,\ldots, N\} \setminus \{i_1,\ldots, i_M\}} s_j$. For instance, if $\tsr{T}$ is an order 4 tensor,
$\tsr{T}(j,k,l,m) = \tsr{T}_{(1,3)}(j,l,k+(m-1)s_2).$

We used calligraphic fonts (e.g., $\proc{P}$) to denote the tensor representing a logical multidimensional processor grid.
Similar to the representation of tensor elements, the index of a specific processor in the grid is denoted in parentheses, e.g. $\proc{P}(i,j)$ denotes one processor indexed by $i,j$ in the 2-dimensional grid.
For a processor grid $\proc{P}$ with size $I_1\times\cdots\times I_N$ and a tensor $\tsr{T}\in\mathbb{R}^{s_1\times\cdots\times s_N}$,
let $x=(x_1,\ldots,x_N)$ denote the index on $\proc{P}$, we use $\tsr{T}_{\proc{P}(x)}$ to denote the local tensor residing on a processor indexed by $x$.
The size of the local tensor will be ${\lceil\frac{s_1}{I_1}\rceil\times\cdots\times \lceil\frac{s_N}{I_N}\rceil}$. When $\frac{s_i}{I_i}$ is not an integer, paddings will be added to the tensor.

\subsection{CP Decomposition with ALS}
\label{sec:bg-cp}

\begin{algorithm}[t]
    \caption{\textbf{CP-ALS}: ALS for CP decomposition}
\label{alg:cp_als}
\begin{algorithmic}[1]
\small
\STATE{
\textbf{Input: }Tensor $\tsr{T}\in\mathbb{R}^{s_1\times\cdots s_N}$,
stopping criteria {$\Delta$}, rank $R$
}
\STATE{Initialize $[\![ \mat{A}^{(1)}, \ldots , \mat{A}^{(N)} ]\!]$ with $\mat{A}^{(i)}\in\mathbb{R}^{s_i\times R}$ as uniformly distributed random matrices within $[0,1]$, $ \mat{S}^{(i)} \leftarrow\mat{A}^{(i)T}\mat{A}^{(i)}$ for $i\in\{1,\ldots,N\}$
}

\STATE{$r\leftarrow 1, r_{\text{old}} \leftarrow 0$ \Comment{Initialize the relative residual}}
\WHILE{$|r - r_{\text{old}}|>{\Delta}$}
\FOR{\texttt{$i\in \inti{1}{N} $}} \label{line:cpals_for}
\STATE\label{line3}{$\boldsymbol{\Gamma}^{(i)}\leftarrow\textbf{S}^{(1)}\ast\cdots\ast \textbf{S}^{(i-1)}\ast \textbf{S}^{(i+1)}\ast\cdots\ast \textbf{S}^{(N)} $}
\STATE{Update $ \textbf{M}^{(i)}$ via dimension tree in Section~\ref{sec:bg-dt}}
\STATE{$   \textbf{A}^{(i)} \leftarrow \textbf{M}^{(i)}\boldsymbol{\Gamma}^{(i)}{}^{\dagger} $}
\vspace{.01in}
\STATE{$   \textbf{S}^{(i)} \leftarrow {\textbf{A}^{(i)}{}^T}\textbf{A}^{(i)} $}
\ENDFOR \label{line:cpals_endfor}

\STATE{$r_{\text{old}} = r$}
\STATE{Update $r$ based on Equation~\eqref{eq:residual}}

\ENDWHILE
\RETURN $[\![ \textbf{A}^{(1)}, \ldots , \textbf{A}^{(N)} ]\!]$
\end{algorithmic}
\end{algorithm}

The goal of the CP tensor decomposition is to minimize the following objective function:
   \[
f(\mat{A}^{(1)}, \ldots , \mat{A}^{(N)}) \coloneqq
 \frac{1}{2}\|\tsr{T}-[\![ \mat{A}^{(1)}, \cdots , \mat{A}^{(N)} ]\!]\|_F^2,
   \]
where
\[
    [\![ \mat{A}^{(1)}, \cdots , \mat{A}^{(N)} ]\!]
    :=\sum_{r=1}^{R} \mat{A}^{(1)}(:,r)\circ \cdots \circ \mat{A}^{(N)}(:,r).
    \]
CP-ALS alternates among subproblems for each of the factor matrices $\mat{A}^{(n)}$. Each subproblem is quadratic, with the optimality condition being setting the subproblem gradient
$\frac{\partial f}{\partial \mat{A}^{(n)}}$
to zero, resulting in the update expression,
     \[
     \mat{A}^{(n)}_{\text{new}}\boldsymbol{\Gamma}^{(n)}= \mat{T}_{(n)}\mat{P}^{(n)},
     \]
where the matrix $\mat{P}^{(n)}\in \mathbb{R}^{I_n \times R}$, with $I_n =
\prod_{i=1,i\neq n}^{N}s_i
$, is formed by Khatri-Rao products of the other factor matrices,
\[
    \mat{P}^{(n)}=\mat{A}^{(N)} \odot \cdots \odot  \mat{A}^{(n+1)}  \odot  \mat{A}^{(n-1)} \odot \cdots \odot \mat{A}^{(1)},
\]
and $\mat{\Gamma}\in\mathbb{R}^{R\times R}$ is computed via a chain of Hadamard products,
\begin{equation}
\boldsymbol{\Gamma}^{(n)}=\textbf{S}^{(1)}\ast\cdots\ast \textbf{S}^{(n-1)} \ast \textbf{S}^{(n+1)}\ast\cdots\ast \textbf{S}^{(N)},
\label{eq:gram}
\end{equation}
\[\text{with each} \quad \textbf{S}^{(i)} = \textbf{A}^{(i)T}\textbf{A}^{(i)}.\]
The MTTKRP computation $\mat{M}^{(n)}=\mat{T}_{(n)}\mat{P}^{(n)}$ is the main computational bottleneck of CP-ALS.
 The computational cost of MTTKRP is $\mathcal{O}(s^NR)$ if $s_n=s$ for all $n\in\inti{1}{N}$.
 The naive implementation of CP-ALS for a dense tensor calculates $N$ MTTKRPs for each ALS sweep, leading to the cost of $\mathcal{O}(Ns^NR)$.
With the dimension tree algorithm, the computational complexity for all the MTTKRP calculations in one ALS iteration is $4s^{N}R$ to leading order in $s$. The dimension tree algorithm will be detailed in Section~\ref{sec:bg-dt}.
Algorithm~\ref{alg:cp_als} presents the CP-ALS procedure described above, performing iterations until the relative decomposition residual of the neighboring sweeps is sufficiently small.
Let $\Tilde{\tsr{T}}$ denote the tensor reconstructed by the factor matrices, the relative residual norm is defined as
\begin{equation}
    r = \frac{\|\tsr{T} - \Tilde{\tsr{T}}\|_F}{\|\tsr{T}\|_F}.
    \label{eq:residual-def}
\end{equation}
As is shown~\cite{ballard2018parallel,liavas2017nesterov,smith2016medium}, $r$ can be calculated efficiently via
\begin{equation}
\small{
    \label{eq:residual}
    r =
\frac{
\sqrt{
\|\tsr{T}\|_F +
\langle \boldsymbol{\Gamma}^{(N)} , \mat{A}^{(N)T}\mat{A}^{(N)}  \rangle
-2\langle \mat{M}^{(N)} , \mat{A}^{(N)}  \rangle
}}{\|\tsr{T}\|_F},
}\end{equation}
assuming that terms $\|\tsr{T}\|_F, \boldsymbol{\Gamma}^{(N)}, \mat{M}^{(N)}$ are all amortized before the residual calculations.

\subsection{The Dimension Tree Algorithm}
\label{sec:bg-dt}

\newsavebox{\dtfigbox}
\begin{lrbox}{\dtfigbox}
\begin{tikzpicture}[>=latex',scale=0.41]

    \tikzstyle{n} = [draw,shape=ellipse,minimum size=1.5em,
                        inner sep=0pt,fill=violet!20]
\node (X) at (137.0bp,234.0bp) [draw,ellipse,n] {$\tsr{T}$};
  \node (M123) at (96.0bp,162.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}^{(1,2,3)}$}};
  \node (M234) at (179.0bp,162.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}^{(2,3,4)}$}};
  \node (M12) at (96.0bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}^{(1,2)}$}};
  \node (M34) at (179.0bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}^{(3,4)}$}};
  \node (M1) at (27.0bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(1)}$}};
  \node (M2) at (99.0bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(2)}$}};
  \node (M3) at (176.0bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(3)}$}};
  \node (M4) at (248.0bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(4)}$}};
  \draw [->] (X) ..controls (122.54bp,208.32bp) and (116.38bp,197.8bp)  .. (M123);
  \draw [->] (X) ..controls (151.67bp,208.56bp) and (158.12bp,197.8bp)  .. (M234);
  \draw [->] (M123) ..controls (96.0bp,135.98bp) and (96.0bp,126.71bp)  .. (M12);
  \draw [->] (M234) ..controls (179.0bp,135.98bp) and (179.0bp,126.71bp)  .. (M34);
  \draw [->] (M12) ..controls (72.081bp,64.735bp) and (59.223bp,51.69bp)  .. (M1);
  \draw [->] (M12) ..controls (97.072bp,63.983bp) and (97.469bp,54.712bp)  .. (M2);
  \draw [->] (M34) ..controls (177.93bp,63.983bp) and (177.53bp,54.712bp)  .. (M3);
  \draw [->] (M34) ..controls (202.92bp,64.735bp) and (215.78bp,51.69bp)  .. (M4);
    \node[left=3em] at (M1)  (l3) {Level 3};
    \node at (l3 |- M12) (l2){Level 2};
    \node at (l3 |- M123) (l1) {Level 1};
\end{tikzpicture}
\end{lrbox}

\newsavebox{\ppfigbox}
\begin{lrbox}{\ppfigbox}
\pgfdeclarelayer{background}
\pgfdeclarelayer{foreground}
\pgfsetlayers{background,main,foreground}
\begin{tikzpicture}[>=latex',scale=0.41]

    \tikzstyle{n} = [draw,shape=ellipse,minimum size=1.5em,
                        inner sep=0pt,fill=violet!20]
\node (X) at (265.95bp,234.0bp) [draw,ellipse,n] {$\tsr{T}$};
  \node (M123) at (150.95bp,162.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(1,2,3)}$}};
  \node (M134) at (265.95bp,162.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(1,3,4)}$}};
  \node (M234) at (380.95bp,162.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(2,3,4)}$}};
  \node (M12) at (101.95bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(1,2)}$}};
  \node (M13) at (27.948bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(1,3)}$}};
  \node (M23) at (175.95bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(2,3)}$}};
  \node (M14) at (249.95bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(1,4)}$}};
  \node (M34) at (323.95bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(3,4)}$}};
  \node (M24) at (397.95bp,90.0bp) [draw,ellipse,n] {\tiny{$\tsr{M}_p^{(2,4)}$}};
  \node (M1) at (101.95bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(1)}$}};
  \node (M2) at (246.95bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(2)}$}};
  \node (M3) at (174.95bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(3)}$}};
  \node (M4) at (323.95bp,18.0bp) [draw,ellipse,n] {\small{$\mat{M}^{(4)}$}};
  \draw [->] (X) ..controls (228.76bp,210.37bp) and (201.74bp,193.92bp)  .. (M123);
  \draw [->] (X) ..controls (265.95bp,207.98bp) and (265.95bp,198.71bp)  .. (M134);
  \draw [->] (X) ..controls (303.13bp,210.37bp) and (330.15bp,193.92bp)  .. (M234);
  \draw [->] (M123) ..controls (133.37bp,135.89bp) and (125.56bp,124.74bp)  .. (M12);
  \draw [->] (M123) ..controls (108.88bp,137.06bp) and (79.072bp,120.1bp)  .. (M13);
  \draw [->] (M123) ..controls (159.86bp,136.06bp) and (163.33bp,126.33bp)  .. (M23);
  \draw [->] (M134) ..controls (260.29bp,136.26bp) and (258.14bp,126.82bp)  .. (M14);
  \draw [->] (M134) ..controls (286.4bp,136.31bp) and (296.15bp,124.55bp)  .. (M34);
  \draw [->] (M234) ..controls (386.96bp,136.26bp) and (389.25bp,126.82bp)  .. (M24);
  \draw [->,dashed,blue!60] (M12) ..controls (101.95bp,63.983bp) and (101.95bp,54.712bp)  .. (M1);
  \draw [->,dashed,blue!60] (M12) ..controls (148.25bp,66.647bp) and (188.51bp,47.209bp)  .. (M2);
  \draw [->,dashed,blue!60] (M13) ..controls (53.768bp,64.575bp) and (67.842bp,51.262bp)  .. (M1);
  \draw [->,dashed,blue!60] (M13) ..controls (74.888bp,66.647bp) and (115.71bp,47.209bp)  .. (M3);
  \draw [->,dashed,blue!60] (M14) ..controls (202.83bp,66.712bp) and (161.01bp,46.935bp)  .. (M1);
  \draw [->,dashed,blue!60] (M14) ..controls (275.77bp,64.575bp) and (289.84bp,51.262bp)  .. (M4);
  \draw [->,dashed,blue!60] (M23) ..controls (200.56bp,64.735bp) and (213.79bp,51.69bp)  .. (M2);
  \draw [->,dashed,blue!60] (M23) ..controls (175.59bp,63.983bp) and (175.46bp,54.712bp)  .. (M3);
  \draw [->,dashed,blue!60] (M24) ..controls (350.12bp,66.83bp) and (306.98bp,46.829bp)  .. (M2);
  \draw [->,dashed,blue!60] (M24) ..controls (372.13bp,64.575bp) and (358.05bp,51.262bp)  .. (M4);
  \draw [->,dashed,blue!60] (M34) ..controls (279.07bp,67.988bp) and (242.51bp,50.856bp)  .. (210.95bp,36.0bp) .. controls (209.17bp,35.161bp) and (207.33bp,34.298bp)  .. (M3);
  \draw [->,dashed,blue!60] (M34) ..controls (323.95bp,63.983bp) and (323.95bp,54.712bp)  .. (M4);
    \node[left=1em] at (M1)  (l3) {};
    \node at (l3 |- M12) (l2){};
    \node at (l3 |- M123) (l1) {};

    \begin{pgfonlayer}{background}
        \draw[rounded corners=2em,line width=3em,blue!20,cap=round]
                (M13.west) -- (M24.east);
    \end{pgfonlayer}
\end{tikzpicture}
\end{lrbox}

\begin{figure*}[]
\centering
\captionsetup[subfloat]{farskip=2pt,captionskip=13pt}
\subfloat[ALS dimension tree with $N=4$]{\usebox{\dtfigbox}
\label{subfig:dt}
}
\subfloat[PP dimension tree with $N=4$]{\usebox{\ppfigbox}
\label{subfig:pp}
}

\caption{Dimension trees for ALS and pairwise perturbation. The blue region in (b) denotes the PP operators.}
\end{figure*}

In each CP-ALS sweep, the TTM and TTV operations for MTTKRP calculations can be amortized and reused.
Such amortization strategies are referred to as dimension tree algorithms.
A dimension tree data structure partitions the mode indices of  an order $N$ tensor hierarchically and constructs the intermediate tensors accordingly~\cite{kaya2019computing,phan2013fast,ballard2018parallel}. The root of the tree corresponds to the input tensor and the leaves consist of all the $N$ factor matrices.
It is assumed in the literature that each ALS sweep uses the same tree.

It has been shown in \cite{kaya2019computing} that for CP decomposition, an optimal dimension tree must be binary. Therefore, our analysis will focus on the binary trees.
We illustrate one dimension tree for $N=4$ in Figure~\ref{subfig:dt}.
The first level contractions (contractions between the input tensor and one factor matrix) are done via TTM.
For an equidimensional tensor with size $s$ and rank $R$,
these contractions have a cost of $\mathcal{O}(s^NR)$ and are generally the most time-consuming part of ALS. Other contractions (transforming one intermediate into another intermediate) are done via batched TTV (also called multi-TTV/mTTV), and the complexity of an $i$th level contraction, where $i<N$,  is $\mathcal{O}(s^{N+1-i}R)$. Because two first level contractions are necessary for the construction of the dimension tree, as is illustrated in Figure~\ref{subfig:dt}, to calculate all the MTTKRP results in one ALS iteration, to leading order in $s$, the computational complexity is $4s^{N}R.$

\subsection{The Pairwise Perturbation Algorithm}
\label{sec:bg-pp}

\begin{algorithm}[]
    \caption{\textbf{PP-CP-ALS}: Pairwise perturbation for CP-ALS}
\label{alg:cp_als_pp}
\begin{algorithmic}[1]
\small
\STATE{\textbf{Input:} tensor $\tsr{T}\in\mathbb{R}^{s_1\times\cdots\times s_N}$,
       stopping criteria $\Delta$, PP tolerance $\epsilon<1$}
\STATE{Initialize $[\![ \textbf{A}^{(1)}, \ldots , \textbf{A}^{(N)} ]\!]$ with $\mat{A}^{(i)}\in\mathbb{R}^{s_i\times R}$ as uniformly distributed random matrices within $[0,1]$, $d\mat{A}^{(i)}\leftarrow \mat{A}^{(i)}$, $ \mat{S}^{(i)} \leftarrow\mat{A}^{(i)T}\mat{A}^{(i)}$ for $i\in\{1,\ldots,N\}$
}
\STATE{$r\leftarrow 1, r_{\text{old}} \leftarrow 0$ \Comment{Initialize the relative residual}}
\WHILE{$|r - r_{\text{old}}|>{\Delta}$}
  \IF{$\forall ~i \in \inti{1}{N}, {\fnrm{d\mat{A}^{(i)}}}<\epsilon{\fnrm{\mat{A}^{(i)}}}$}
    \FOR{\texttt{$i\in \inti{1}{N} $}}
      \STATE{$\mat{A}_p^{(i)} \gets \mat{A}^{(i)}$, $d\mat{A}^{(i)} \gets \mat{O}$}
    \ENDFOR
    \STATE{Compute $\tsr{M}^{(i,n)}_p,\mat{M}^{(n)}_p$ for $i,n\in \inti{1}{N}$ via dimension tree \label{line:pp_init_step}}
    \WHILE{$\forall ~i \in \inti{1}{N}, \fnrm{d\mat{A}^{(i)}}<\epsilon\fnrm{\mat{A}^{(i)}}$}
      \FOR{\texttt{$j\in \inti{1}{N} $}}
        \STATE{$\boldsymbol{\Gamma}^{(j)}\leftarrow\mat{S}^{(1)}\ast\cdots\ast \mat{S}^{(j-1)}\ast \mat{S}^{(j+1)}\ast\cdots\ast \mat{S}^{(N)} $}
        \STATE{
        Update $\Tilde{\mat{M}}^{(j)}$ based on Equation~\eqref{eq:ppupdate}
         }
        \STATE{$   \mat{A}^{(j)} \leftarrow \Tilde{\mat{M}}^{(j)}\boldsymbol{\Gamma}^{(j)}{}^{\dagger} $}
        \STATE{$d\mat{A}^{(j)} = \mat{A}^{(j)} -\mat{A}^{(j)}_p$, $   \mat{S}^{(j)} \leftarrow {\mat{A}^{(j)}}{}^T\mat{A}^{(j)} $}
      \ENDFOR
    \ENDWHILE
  \ENDIF \label{line:pp_endif}
  \STATE{Perform a regular ALS sweep as in Algorithm~\ref{alg:cp_als} (line \ref{line:cpals_for}-\ref{line:cpals_endfor}), taking $d\mat{A}^{(i)}$ as the update of $\mat{A}^{(i)}$ in one sweep for each $i\in\inti{1}{N}$ \label{line:regular_als}}
  \STATE{$r_{\text{old}} = r$}
  \STATE{Update $r$ based on Equation~\eqref{eq:residual}}
\ENDWHILE
\RETURN $[\![ \mat{A}^{(1)}, \ldots , \mat{A}^{(N)} ]\!]$
\end{algorithmic}
\end{algorithm}

Before the introduction of PP, we define the partially contracted MTTKRP intermediates $\tsr{M}^{(i_1,i_2,\ldots,i_m)}$ as follows,
\begin{equation}
\small{
\tsr{M}^{(i_1,i_2,\ldots,i_m)} = \tsr{T}_{(i_1,i_2,\ldots,i_m)}\bigodot_{j\in {\inti{1}{N}}\setminus\{i_1,i_2,\ldots, i_m\}}\mat{A}^{(j)},}
\label{eq:tensors-cp}
\end{equation}
where $\tsr{M}^{(1,\ldots, N)}$ is the input tensor $\tsr{T}$. Let $\mat{A}_p^{(n)}$ denote the $\mat{A}^{(n)}$ calculated with regular ALS at some number of sweeps prior to the current one,
we also define $\tsr{M}_p^{(i_1,i_2,\ldots,i_m)}$
in the same way as $\tsr{M}^{(i_1,i_2,\ldots,i_m)}$ in Equation~\eqref{eq:tensors-cp}, except that $\tsr{T}$ is contracted with $\mat{A}_p^{(j)}$ for $j\in \inti{1}{N} \setminus \{i_1,i_2,\ldots,i_m\}$.

Pairwise perturbation (PP) uses perturbative  corrections to the subproblems rather than recomputing the tensor contractions and contains two steps.
The initialization step calculates the PP operators $\tsr{M}_p^{(i,j)}$ for $ \forall i,j\in\{1,\ldots, N\}, i<j$.
Similar to CP-ALS, computation of these operators can also benefit from dimension trees.
Figure~\ref{subfig:pp} describes the PP dimension tree for $N=4$.
In the PP dimension tree, ${l+1 \choose 2}$ tensors $\tsr{M}_p^{(i,j,j+1,\ldots, j+N-l-1)}, \forall i,j\in \inti{1}{l+1}, i<j$ are calculated at the $l$th level.
The construction of PP operators with the dimension tree costs $4s^NR$ to the leading order, which is computationally the same expensive as the ALS dimension tree algorithm\footnote{Note that despite 3 first level intermediates are needed, only two of them need to be recalculated, and the remaining one (e.g. $\tsr{M}_p^{(2,3,4)}$ in Figure~\ref{subfig:pp}) can be amortized from the last DT sweep.}.

The approximated step uses the PP operators to approximate the MTTKRP $\mat{M}^{(n)}$ with $\Tilde{\mat{M}}^{(n)}$ as follows,
\begin{equation}
    \Tilde{\mat{M}}^{(n)}
    =\mat{M}_p^{(n)} + \sum_{i=1,i\neq n}^{N}\mat{U}^{(n,i)}
    + \mat{V}^{(n)},
   \label{eq:ppupdate}
\end{equation}
\begin{equation}
\text{where} \quad    \mat{U}^{(n,i)}(x,k) = \sum_{y=1}^{s_i}\tsr{M}_p^{(n,i)}(x,y,k) d\mat{A}^{(i)}(y,k),
\label{eq:U_ni}
\end{equation}
\vspace{-3mm}
\begin{equation}
\small{
    \mat{V}^{(n)} = \mat{A}^{(n)} \bigg(
    \sum_{i,j=1\neq n, i<j}^{N}
    d\mat{S}^{(i)} * d\mat{S}^{(j)} * \bigast_{k=1, k\neq i,j,n}^{N}\mat{S}^{(k)} \bigg),
}
\label{eq:V_nij}
\end{equation}
\begin{equation}
\text{and} \quad  d\mat{S}^{(i)} = \mat{A}^{(i)T} d\mat{A}^{(i)}.
\label{eq:ds}
\end{equation}
Terms $\mat{U}^{(n,i)}$ are the first-order corrections computed via
the PP operators, and the term $\mat{V}^{(n)}$ is the second-order correction to lower the error to a greater extent.
Given $\tsr{M}_p^{(n,i)}$ and $\mat{M}_p^{(n)}$, calculation of $\Tilde{\mat{M}}^{(n)}$ for $n\in \inti{1}{N}$ requires $2N(Ns^2R+NR^2 + sR^2)$ operations overall. Algorithm~\ref{alg:cp_als_pp} presents the PP-CP-ALS method described above. We direct readers to Section 3.1 in reference~\cite{ma2018accelerating} for an illustration of the algorithm on order 3 tensors.

\subsection{Parallel CP-ALS}
\label{subsec:par-als}
\begin{algorithm}
\caption{\textbf{Par-CP-ALS}: Parallel CP-ALS}
\label{alg:Par-CP-ALS}
\begin{algorithmic}[1]
\small
\STATE{
\textbf{Input: }Processor grid $\proc{P}$ with dimension $
I_1\times\cdots\times I_N$, where $I=\prod_{i=1}^N I_i$, tensor $\tsr{T}\in\mathbb{R}^{s_1\times\cdots s_N}$ distributed over $\proc{P}$
}
\STATE{$\proc{Q}\leftarrow \proc{P}$ reshaped to a 2-d array with dimension $I\times 1$}
\STATE{\Comment{$x$ denotes one processor in the grid whose index is $(x_1,\ldots,x_N)$ in $\proc{P}$, and the index is $(x, 1)$ in $\proc{Q}$}}
\FOR{\texttt{$i\in \inti{2}{N} $}}
	\STATE Initialize $\mb{A}{i}_{\proc{Q}(x)}\in \mathbb{R}^{\lceil \frac{s_i}{I}\rceil\times R}$
	\STATE $\mat{S}^{(i)}_{\proc{Q}(x)} \leftarrow \mat{A}^{(i)T}_{\proc{Q}(x)}\mt{A}{i}{\proc{Q}(x)}$
	\STATE $\mat{S}^{(i)}_{\proc{Q}(x)} \leftarrow \text{All-Reduce}(\mat{S}_{\proc{Q}(x)},\textsc{All-Procs})$ \label{line:all-reduce1}
	\STATE $\mb{A}{i}_{\proc{P}(x)} \leftarrow \text{All-Gather}(\mb{A}{i}_{\proc{Q}(x)},\textsc{Proc-Slice}(\proc{P}_{(i)}(x_i, :))$\label{line:all-gather1}
\ENDFOR
\WHILE{Stopping criteria not reached}
    \FOR{\texttt{$i\in \inti{1}{N} $}}
        \STATE{$\boldsymbol{\Gamma}^{(i)}_{\proc{Q}(x)}\leftarrow\mat{S}^{(1)}_{\proc{Q}(x)}\ast\cdots\ast \mat{S}^{(i-1)}_{\proc{Q}(x)}\ast \mat{S}^{(i+1)}_{\proc{Q}(x)}\ast\cdots\ast \mat{S}^{(N)}_{\proc{Q}(x)} $}
        \STATE{$ \mat{M}^{(i)}_{\proc{P}(x)}\leftarrow \text{Local-MTTKRP}(\tsr{T}_{\proc{P}(x)}, \{\mt{A}{1}{\proc{P}(x)},\ldots,\mt{A}{N}{\proc{P}(x)}\}, i)$ via dimension tree in Section~\ref{sec:bg-dt}
        \label{line:local-mttkrp}
        }
        \STATE{$ \mat{M}^{(i)}_{\proc{Q}(x)}\leftarrow
        \text{Reduce-Scatter}(\mat{M}^{(i)}_{\proc{P}(x)}, \textsc{Proc-Slice}(\proc{P}_{(i)}(x_i, :)))
        $
        \label{line:reduce-scatter}
        }
        \STATE{$  \mt{A}{1}{\proc{Q}(x)} \leftarrow \mat{M}^{(i)}_{\proc{Q}(x)}\boldsymbol{\Gamma}_{\proc{Q}(x)}^{(i)\dagger} $}
        \vspace{.01in}
        \STATE{$   \mat{S}^{(i)}_{\proc{Q}(x)} \leftarrow \mat{A}_{\proc{Q}(x)}^{(i)T}\mat{A}^{(i)}_{\proc{Q}(x)} $}
    	\STATE $\mat{S}^{(i)}_{\proc{Q}(x)} \leftarrow \text{All-Reduce}(\mat{S}_{\proc{Q}(x)},\textsc{All-Procs})$ \label{line:all-reduce2}
    	\STATE $\mb{A}{i}_{\proc{P}(x)} \leftarrow \text{All-Gather}(\mb{A}{i}_{\proc{Q}(x)},\textsc{Proc-Slice}(\proc{P}_{(i)}(x_i, :))$ \label{line:all-gather}
	\ENDFOR
\ENDWHILE
\RETURN $[\![ \mat{A}^{(1)}, \ldots , \mat{A}^{(N)} ]\!]$.
\end{algorithmic}
\end{algorithm}

We use the BSP $\alpha-\beta-\gamma$ model  for parallel cost analysis~\cite{valiant1990bridging,thakur2005optimization}. In addition to considering the communication cost of sending data among processors (horizontal communication cost), we use another parameter, $\nu$, to measure the cost of transferring data between slow memory and cache (vertical communication cost)~\cite{solomonik2017communication}.
$\alpha$ represents the cost of sending/receiving a single message, $\beta$ represents the cost of moving a single word among processors,
$\nu$ represents the cost of moving a single word between the main memory and cache,
and $\gamma$ represents the cost to perform one arithmetic operation. We assume $\alpha \gg \beta \gg \gamma$, and $\nu \leq \gamma \cdot \sqrt{H}$, where $H$ is the cache size. We summarize the collective routines on a fully-connected network used in the parallel algorithms, including All-Gather, Reduce-Scatter and All-Reduce, as follows:
\begin{itemize}
    \item $\text{All-Gather}(v, \textsc{Procs})$ collects data $v$ distributed across $P$ processors ($\textsc{Procs}$) and stores the concatenation of all the data with size $n$ redundantly on all processors. Its cost is $\log P \cdot \alpha + n\delta(P) \cdot \beta $, where $\delta(P)=1$ if $P>1$, otherwise $0$.
    \item $\text{Reduce-Scatter}(v, \textsc{Procs})$ sums $v$ distributed across $\textsc{Procs}$ and partitions the result across $\textsc{Procs}$. Its cost is $\log P \cdot \alpha + n\delta(P) \cdot \beta $.
    \item $\text{All-Reduce}(v, \textsc{Procs})$ sums $v$ distributed across $\textsc{Procs}$ and stores the result redundantly on all processors. Its cost is $2\log P \cdot \alpha + 2n\delta(P) \cdot \beta $.
\end{itemize}

Our parallel algorithms for CP-ALS on dense tensors are based on Algorithm~\ref{alg:Par-CP-ALS}, which is introduced in~\cite{ballard2018parallel,eswar2019planc}. The input tensor $\tsr{T}$ with order $N$ is uniformly distributed across an order $N$ processor grid $\proc{P}$, and all the factor matrices are initially distributed such that each processor owns a subset of the rows. The main idea of the algorithm is to
decompose the MTTKRP into local MTTKRP calculations to reduce the expensive communication cost, e.g.,
if $\mat A^{(1)} = \text{MTTKRP}(\tsr{T}, \mat{A}^{(2)}, \mat{A}^{(3)})$ then
\[
\small
\mat A_{\proc{P}(i,j,k)}^{(1)} = \sum_{j,k} \text{Local-MTTKRP}(\tsr{T}_{\proc{P}(i,j,k)}, \mat{A}^{(2)}_{\proc{P}(i,j,k)}, \mat{A}^{(3)}_{\proc{P}(i,j,k)}),\]
\normalsize
where $i,j,k$ denote the location of a processor in a 3D grid.
Before the MTTKRP calculation, all the factor matrices are redistributed (lines~\ref{line:all-gather1},\ref{line:all-gather}). For the $i$th mode factor matrix $\mat{A}^{(i)}$, all processors having the same $i$th index in the processor grid $\proc{P}$ redundantly own the same $\lceil\frac{s_i}{I_i}\rceil$ rows of $\mat{A}^{(i)}$.
This setup prepares all the local factor matrices $\mt{A}{1}{\proc{P}(x)},\ldots,\mt{A}{N}{\proc{P}(x)}$ necessary for a local MTTKRP on each processor indexed $x$. The local MTTKRP routine (line~\ref{line:local-mttkrp}) independently performs MTTKRP calculations on each processor, and this step requires no communication. The local MTTKRP can be efficiently calculated with the dimension tree techniques. After the local MTTKRP, Reduce-Scatter (line~\ref{line:reduce-scatter}) is performed to sum-up the local contributions and the MTTKRP outputs $\mat{M}^{(i)}$ are distributed such that each processor owns a subset of the rows. In addition, all the Gram matrices $\mat{S}^{(i)}$, once updated, are then distributed redundantly on all the processors via All-Reduce (lines~\ref{line:all-reduce1},\ref{line:all-reduce2}), allowing for the linear systems to be solved locally.

For each processor, the leading order computational cost is $\frac{4s^NR}{P}$, if the dimension size is $s$ and the state-of-art dimension tree algorithm is used. Three collective routines (lines~\ref{line:reduce-scatter},\ref{line:all-reduce2},\ref{line:all-gather}) are called for each factor matrix update. When $I_1=\cdots=I_N=P^{\frac{1}{N}}$, the horizontal communication cost for each ALS sweep is $\mathcal{O}(N\log(P)\cdot\alpha + N(sR/P^{\frac{1}{N}} + R^2)\cdot\beta)$.

Unlike Algorithm~\ref{alg:Par-CP-ALS}, our implementation calculates all the Hadamard products and the linear system solves in a parallel way, leveraging
a distributed-memory matrix library for solving symmetric positive definite linear systems.
Distributing the work in the solve reduced the computational and bandwidth costs, while raising the latency cost.
Our performance evaluation in Section~\ref{subsec:bench} also includes the PLANC implementation of CP-ALS~\cite{eswar2019planc}, which makes use of a sequential linear system solve.
As we will show,
the cost of solving linear systems is often small for both approaches,
considering that the MTTKRP calculations are the major bottleneck.

\section{Acknowledgements}
Linjian Ma and Edgar Solomonik were supported by the US NSF OAC SSI program, award No.\ 1931258.
This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is supported by National Science Foundation grant number ACI-1548562.
We used XSEDE to employ Stampede2 at the Texas Advanced Computing Center (TACC) through allocation TG-CCR180006.

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

\section{Background}
\label{sec:background}
\input{background}

\section{Multi-Sweep Dimension Tree}
\label{sec:pp-msdt}
\input{pp-msdt}

\section{Parallel Algorithms}
\label{sec:par-alg}
\input{parallel-alg}

\section{Experimental Results}
\label{sec:results}
\input{results}

\section{Conclusion}
\label{sec:conclu}
\input{conclusion}

\bibliographystyle{abbrv}

\subsection{Implementations, Platforms and Tensors}

We implement parallel DT, MSDT and PP algorithms with Cyclops Tensor Framework (v1.5.5)~\cite{solomonik2014massively}, which is a distributed-memory library for matrix/tensor contractions that uses MPI for interprocessor communication and OpenMP for threading. On each processor, we use Intel compilers and the MKL library for threaded BLAS routines, including batched BLAS routines, which are efficient for mTTV arising in MTTKRP, and employ the HPTT library~\cite{springer2017hptt} for high-performance tensor transpositions.
We also use a wrapper provded by Cyclops for ScaLAPACK~\cite{Dongarra:1997:SUG:265932} routines to solve symmetric positive definite linear systems of equations\footnote{All of our code is available at \url{https://github.com/LinjianMa/parallel-pp}.}. All storage and computations assume the tensors are dense. Our PP algorithm calls the MSDT subroutine for the regular ALS sweeps (line~\ref{line:regular_als} in Algorithm~\ref{alg:cp_als_pp}) to improve the performance.

The experimental results are collected on the Stampede2 supercomputer located at the University of Texas at Austin.
Experiments are performed on the Knight's Landing (KNL) nodes, each of which consists of 68 cores, 68 threads, 96 GB of DDR RAM, and 16 GB of MCDRAM.
These nodes are connected via a 100 Gb/sec fat-tree Omni-Path interconnect.

We compare the performance of different algorithms on both synthetic tensors and application datasets.
The application datasets we considered include publicly available tensor datasets as well as tensors of interest for quantum chemistry calculations.
These tensors enable us to demonstrate the effectiveness of our algorithms on practical problems.
We use the following four tensors to test the performance. For all the experiments, we use 16 processors on each KNL node, and each processor uses 4 threads.
\begin{enumerate}[leftmargin=*]
    \item \label{tsr:col} \textbf{Tensors with given collinearity}~\cite{battaglino2017practical}. We create tensors based on randomly-generated factor matrices $\mat{A}^{(n)}$, where $n\in\{1,\ldots,N\}$. Each factor matrix $\mat{A}^{(n)} \in \mathbb{R}^{s\times R}$ is randomly generated so that the columns have collinearity defined based on a scalar $C$ (selected randomly from a given interval $[a,b)$),
$$
\frac{\langle \mat{a}_i^{(n)}, \mat{a}_j^{(n)}\rangle}{\vnrm{\mat{a}_i^{(n)}}\vnrm{\mat{a}_j^{(n)}}}
=C, \quad \forall i,j \in \{1, \ldots, R\}, i\neq j.
$$
The generated tensor has dimension size $s$ in each mode, and its CP rank is bounded by $R$.
Higher collinearity corresponds to greater overlap between columns within each factor matrix, which makes the convergence of the rank-$R$ CP-ALS procedure slower~\cite{rajih2008enhanced}.
We experiment on tensors with dimensions $1600\times 1600\times 1600$. We run the experiments on 64 processors, and the processor grid has dimension $4 \times 4 \times 4$.
\item \label{tsr:quantum}\textbf{Quantum chemistry tensor.} We also test on the density fitting intermediate tensor arising in quantum chemistry, which is the Cholesky factor of the two-electron integral tensor~\cite{hohenstein2012tensor,hummel2017low}. For the order 4 two-electron integral tensor $\tsr{T}$, its Cholesky factor is an order 3 tensor $\tsr{D}$, with their element-wise relation shown as follows:
\[
\tsr{T}(a,b,c,d) = \sum_{e=1}^{E}\tsr{D}(a,b,e)\tsr{D}(c,d,e),
\]
where $E$ is the third mode dimension size of $\tsr{D}$.
CP decomposition can be performed on $\tsr{D}$ to compress the intermediate and can accelerate the post Hartree-Fork calculations~\cite{hohenstein2012communication}. We generate the density fitting tensor via the PySCF library~\cite{sun2018pyscf}, which represents the compressed restricted Hartree-Fock wave function of an 40 water molecule chain system with a STO-3G basis set. The generated tensor has size $4520\times 280\times 280$. We run the experiments on 32 processors, and the processor grid has dimension $8 \times 2 \times 2$.
\item  \label{tsr:coil} \textbf{COIL dataset}. COIL-100 is an image-recognition dataset that contains images of objects in different poses~\cite{nenecolumbia}. It has been used previously as a tensor decomposition benchmark~\cite{battaglino2017practical,zhou2014decomposition,ma2018accelerating}.
Transferring the data into the tensor format, the generated tensor has size $128\times 128\times 3\times 7200$. We run the experiments on 16 processors, and the processor grid has dimension $2 \times 4 \times 1 \times 2$.
\item \label{tsr:timelapse}  \textbf{Time-Lapse hyperspectral radiance images}. We consider the 3D hyperspectral imaging dataset called "Souto wood pile"~\cite{nascimento2016spatial}. The dataset is usually used on the benchmark of nonnegative tensor decomposition~\cite{liavas2017nesterov,ballard2018parallel}. The hyperspectral data consists of a tensor with dimensions $1024\times1344\times33\times 9$. We run the experiments on 16 processors, and the processor grid has dimension $4 \times 4 \times 1 \times 1$.
\end{enumerate}

\begin{figure}[]
\centering
\includegraphics[width=0.43\textwidth, keepaspectratio]{pic/col-3d.pdf}
\caption{Relation between PP speed-ups and input collinearity for order 3 tensors. The dimension size $s=1600$, the rank $R=400$, and the experiments run on the $4\times 4\times 4$ processor grid. The PP tolerance is set as 0.2. Each box is based on 5 experiments with different random seeds and shows the 25th-75th quartiles. The median is indicated by a horizontal line inside the box and outliers are displayed as dots.
}
\label{fig:box}
\end{figure}
\begin{table}[]
\caption{
Detailed statistics of the results shown in Figure~\ref{fig:box}. From left to right: the tensor configuration (Col stands for collinearity), number of exact ALS sweeps, number of PP initialization sweeps and number of PP approximated sweeps. All the data are the average statistics from 5 experiments.
}
\label{table:randomstat}
\centering
\begin{adjustbox}{width=.42\textwidth}
\begin{tabular}{|c|c|c|c|}
  \hline
  Configuration
 & Num-ALS
 & Num-PP-init
 & Num-PP-approx
 \\
  \hline
Col$\in[0.0, 0.2)$ & 21.2 & 1.4 & 14.4  \\
  \hline
Col$\in[0.2, 0.4)$ & 50.8 & 11.6 & 39.6 \\
  \hline
Col$\in[0.4, 0.6)$ & 65.6 & 29.0 & 169.6 \\
  \hline
Col$\in[0.6, 0.8)$ & 34.8 & 17.4 & 180.2 \\
  \hline
Col$\in[0.8, 1.0)$ & 10.2 & 3.4 & 22.8 \\
  \hline
\end{tabular}
\end{adjustbox}
\end{table}

\subsection{Benchmarks}
\label{subsec:bench}

We perform a parallel scaling analysis to compare
the per-ALS sweep simulation time for DT, MSDT, the PP initialization step and the PP approximated step, and the results are presented in Figure~\ref{fig:benchmark}. We also show the simulation time using PLANC~\cite{eswar2019planc} for reference, which contains the state-of-art parallel DT implementations. The benchmarks are performed on both order 3 and order 4 tensors.

We show the order 3 weak scaling results in Figure~\ref{subfig:weakscale-3d}.
As can be seen, the performance of our DT implementation is comparable, and slightly better than PLANC. MSDT performs consistently better than DT. Under the largest processor grid configuration, MSDT is 1.25X better than DT. In addition, the time spent on each PP initialization step is consistently less than each DT sweep, and the PP approximated step achieves a speed-up of $1.94$X compared to DT under the largest processor grid, showing the good scalability of our parallel PP algorithm. We show the detailed time breakdown under the grid configurations $2\times 4 \times 4$, $8\times 8 \times 8$ in Figure~\ref{subfig:timebreak-3d1},\ref{subfig:timebreak-3d2}. The TTM is the major bottleneck for all the kernels except the PP approximated step, which is bounded by the mTTV kernel. Note that
as is discussed in Section~\ref{sec:par-alg}, the mTTV kernel is vertical communication (memory bandwidth) bound, resulting in less experimental speed-ups despite the large speed-ups in terms of the flop counts.

We show the order 4 weak scaling results in Figure~\ref{subfig:weakscale-4d}.
Considering that the PP initialization step for the order 4 tensors involves several tensor transposes, we use 8 processors per KNL node and 8 threads per processor for the benchmark, so that the transposes can be accelerated with  a relatively large number of
threads on each processor.
The performance of our DT implementation is comparable to PLANC for most of the processor grid configurations. When the number of processors used is large, our DT implementation is slightly slower than PLANC. This can be explained by the slow global linear system solves shown in Figure~\ref{subfig:timebreak-4d2}.
Since the CP rank is relatively small, using too many processors results in over-parallelization and the horizontal communication cost increases. MSDT performs consistently better than DT, and achieves a speed-up of 1.10X under the largest processor grid configuration. In addition, the PP initialization step is much slower than the DT sweep, which is due to several tensor transposes in the mTTV kernels. It also accounts for the slow mTTV kernels shown in Figure~\ref{subfig:timebreak-4d1},\ref{subfig:timebreak-4d2}. The PP approximated step achieves a speed-up of $1.44$X compared to DT under the largest processor grid. Overall, the speed-up of PP is less on order 4 compared to order 3 tensors.

We also show the per-sweep MTTKRP calculation time comparison between our parallel PP implementation and that in~\cite{ma2018accelerating} in Table~\ref{table:compare_with_ma2018}. As can be seen, the current implementation is more efficient for both kernels under all the processor grid configurations. The local dimension tree calculations greatly decrease the horizontal communication cost.

\subsection{Performance Comparison}

\begin{figure}[]
\label{fig:real}
\centering

\subfloat[Col$\in[0.6, 0.8)$, $R=400$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/random_detail.pdf}\label{detail:random}}
\subfloat[Chemistry, $R=300$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/chem_r300.pdf}\label{detail:chem_r300}}

\subfloat[Chemistry, $R=600$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/chem_r600.pdf}\label{detail:chem_r600}}
\subfloat[Chemistry, $R=1000$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/chem_r1000.pdf}\label{detail:chem_r1000}}

\subfloat[Coil dataset, $R=20$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/coil.pdf}\label{detail:coil}}
\subfloat[Time-lapse dataset, $R=50$]{\includegraphics[width=0.24\textwidth, keepaspectratio]{pic/timelapse.pdf}\label{detail:timelapse}}

\caption[]{
Comparison of PP, MSDT, DT on different tensors.
}
\label{fig:detail_comparison}
\end{figure}

\begin{table}[]
\caption{
Detailed statistics of the results shown in Figure~\ref{fig:detail_comparison}. From left to right: the tensor type, number of ALS sweeps until PP experiments are finished, number of PP initialization sweeps, number of PP approximated sweeps, the average time of each ALS sweep, the average time of each PP initialization sweep, and the average time of each PP approximated sweep.
}
\label{table:detail-run}
\centering
\begin{adjustbox}{width=.49\textwidth}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
  Tensor
 & N-ALS
 & N-PP-init
 & N-PP-approx
 & T-ALS
 & T-PP-init
 & T-PP-approx
 \\
  \hline
Figure~\ref{detail:chem_r300} & 96 & 39 & 477 & 0.5064 & 0.2335 & 0.3443 \\
  \hline
Figure~\ref{detail:chem_r600} & 76 & 29 & 468 & 0.8177 & 0.3801  & 0.5839 \\
  \hline
Figure~\ref{detail:chem_r1000} & 216  & 63 & 1129 & 1.4307 & 0.795 & 1.1095 \\
  \hline
Figure~\ref{detail:coil} & 34  &  11 & 115 & 2.3907 & 4.2253 & 0.1785 \\
  \hline
Figure~\ref{detail:timelapse} & 30 & 10 & 155 & 0.6703 & 0.3631 & 0.1554 \\
  \hline
\end{tabular}
\end{adjustbox}
\end{table}

We test algorithms on both the synthetic tensors (Tensor~\ref{tsr:col}) and real datasets (Tensor~\ref{tsr:quantum},\ref{tsr:coil},\ref{tsr:timelapse}). We use the metrics relative residual, $r$ (defined in Equation~\eqref{eq:residual-def}), and fitness, $f=1-r$, to evaluate the convergence progress of the decomposition.  Figures~\ref{fig:box} shows the speed-up distribution with different exact factor matrices collinearity. We stop the algorithm when the stopping tolerance (defined as the fitness difference between two neighboring sweeps) reaches $10^{-5}$, or the maximum number of iterations (300) is reached.
It can be seen that PP achieves up to 1.8X speed-up compared to DT. In addition, PP tends to have higher speed-ups when the collinearity is within $[0.4, 0.8)$. This is because tensors within above collinearity range will converge in more sweeps, and more PP approximated sweeps are activated, as can be seen in Table~\ref{table:randomstat}.
When the collinearity is in the range of $[0.0, 0.4)$ and $[0.8, 1.0)$, the experiments stop in small number of sweeps, which results in less benefit of PP.
In addition, we show the fitness-time relation for one experiment with the collinearity$\in[0.6, 0.8)$ in Figure~\ref{detail:random}. As can be seen, the fitness increases monotonically, indicating that PP controls the approximation error well.
The results show that substantial performance gains on large synthetic tensors can be achieved for PP under the parallel execution, which is a supplement to the results in \cite{ma2018accelerating}, which shows that PP can speed-up CP decomposition on small (each tensor has size $400\times 400\times 400$) synthetic tensors.

We also compare the performance on application tensors. The PP tolerance is set as 0.1 for these tensors. Figure~\ref{detail:chem_r300},\ref{detail:chem_r600},\ref{detail:chem_r1000} show the results on the quantum chemistry tensor with different CP ranks.
The detailed statistics are shown in Table~\ref{table:detail-run}.
As is shown in the figures, for all the variants of the CP ranks, PP performs
better than DT, achieving 1.52-1.78X speed-ups.
Figure~\ref{detail:coil},\ref{detail:timelapse} show the results on the image datasets. The detailed statistics are shown in Table~\ref{table:detail-run}.
As is shown in the figures, PP achieves 2.4X speed-up on the Coil dataset and 5.4X speed-up on the Time-lapse dataset.

redpajama_set_name: RedPajamaArXiv


Sharing a simple technique on how to apply one eyeshadow shade on the eyes while still looking like all made up. It's very easy and I like to do this whenever I'm in a hurry.
1. Choose a neutral eyeshadow shade. I prefer using a brown eyeshadow shade to achieve this look.
2. Apply eye primer on your entire eyelids. Personally, I prefer using Paul & Joe's eye gloss duo instead of an eye primer. I only use the glossy end of the eye gloss duo to act as my primer. At times I'd also add the shimmery end of the eye gloss duo on my eyelids.
You might want to check out my review of Paul & Joe's eye gloss duo from this link.
3. Apply the neutral eyeshadow shade on your crease and on the outer corners of your eyes.
4. Blend, blend, blend. Soften the harsh edges. Move outwards extending the color to the outer corners of your eyes, fading it naturally. It should look smokey.
5. Apply eyeliner and mascara. Continue with makeup on the rest of the face.


they sucked me in and I'm drowning.
No escape for me, no no one can set me free!
I've joined the chain you see, oh the dream its still burning brightly.
I feel that I sold out, compromise they shout.
You can't do that they're saying.
but now is here and I'm burning.
No going back for me, there's nowhere that I can see.
I mustn't stop, don't give up, it took too long to make it.
I mustn't stop, don't give in, don't give it away.
The whole world is turning, time it keeps moving.
Its hard to see what I'm learning.
My soul's been sold and I'm burning.
Its uncertainty that just will not let me go.
It mustn't get to me oh that dream is still burning brightly.


You're TOOOO funny! I couldn't agree more about markets -- Sorry Houston -- not my favorite. SLC is definitely my favorite though -- could be because I was born in Utah? Or because I have family there? Or maybe because my oldest is going to move there in a year? Oh Wait -- I don't love Utah for that because it will put a 25 hour drive between me and my new grandbaby -- BoooHisssss! But, other than that, the mountain views are spectacular and the quilt shops are divine. My time at market will be short, but I'm hoping to sneak up on you!!! Rent a car and drive to the mountains -- we drive on the RIGHT side of the road LOLOL!!!
The salt lake smells disgusting.
The world is dafter with you in it dear, and the more you travel the dafter it gets.
That orange blender of yours is a bit good.
I'm glad you have decided to continue your trip anyway and the fact Mr RicRac is coming as well is a good thing. Just make sure his case has lots of room for all the goodies you will bring home. Who needs excess luggage allowances?
Utah, apparently good for big, wide open spaces away from Salt Lake. The spiritual home of Mormonism.
According to Trip Advisor, there are some awesome things out in the boondocks to see in Utah. If you have a bit of time to spend after QM, have a look around.
But, whatever you do decide to do : Enjoy!
I've been to Houston but can't remember it smelling of poo - I think I only changed planes there actually. Never been to Utah but the name sounds so 'American' if you know what I mean. I expect there will be peanut butter though. Have a brilliant time showing off your lovely new fabric and those 'on trend' flamingos.
You always make me laugh! I've never been to Houston so can't vouch for the poo scent but anyplace that is that hot and humid can't help but be smelly, IMHO. I've been to a tiny corner of Utah many years ago but luckily was with my Grandmother and my own small children so none of the exciting alternatives came up. Hope you and the Mister have the most wonderful of experiences in the high country of SLC, Utah! Your designs are slaying me with adorableness in the peeks you have permitted.


your guides are Award winning Photographers Mike Langford or Jackie Ranken.
The landscape throughout Skippers Canyon, once the richest gold mining area in the world, is ruggedly spectacular and best seen in autumn when the trees are ablaze with colour and in Summer when the light can reach deep into the valley turning the Shotover River into a blue azure strip of colour. Our four wheel drive (4WD) Photo Safari follows the narrow winding road that serviced the gold fields, once home to thousands of miners. All that remains of this era is a beautifully restored School House and the sculptured landforms produced by the gold diggings.
Your tutors Mike Langford or Jackie Ranken will help you learn how to take your camera off automatic and to fully utilise your camera in a practical and logical way. Much of the day is spent discussing composition and solving any photographic problem that arises. The day is spent photographing in places suited to the weather conditions, allowing everyone time and circumstance to express their own vision, and at the same time receive constructive and appropriate critiques of their images.
The best way to learn about Photography is to be guided through a range of photographic ideas and then receive immediate and appropriate feedback from your highly experienced and awarded instructor /guides. Mike and Jackie offer photography instruction, they do not just take you to places.


text:
– the next reincarnation of the Dalai Lama
Michael Ruark May 8, 2022 May 8, 2022 Knowledge, Peace, Religion, World
A couple of years ago, during a meeting of Tibetan leaders in Dharamshala in India, Tenzin Gyatso, the 14th Dalai Lama, was asked about his reincarnation. Addressing the room of monks, religious teachers and Tibetan politicians, the Dalai Lama asked them to look into his eyes. "Do you think it's time now?" he asked.
It was a meeting that would end with the Tibetan leaders agreeing that the issue of reincarnation was one that would be decided only by the Dalai Lama himself. But China, which annexed Tibet in 1951 and has retained tight control over the region ever since, has other ideas. It insists that the choice of the next Dalai Lama lies only with China, and have even enshrined this right into Chinese law.
The Dalai Lama, who recently turned 86, has insisted that discussions of his death are premature (according to his own visions, he will live to 113). But a power struggle for who will choose his reincarnation after he dies has already begun.
"We are looking at the highly likely situation that when the 14th Dalai Lama dies, there will be two Dalai Lamas named in his place," said Robert Barnett, a Tibetan expert. "One selected on the basis of instructions left behind by His Holiness the Dalai Lama and one chosen by the Chinese Communist party."
Yet China is not the only country now keeping a watchful eye on the Dalai Lama's succession. Since 1959, the Dalai Lama has lived in exile in Dharamshala, nestled in the Himalayas, and Tibet has remained a sensitive factor in India's relationship with China, with whom it shares a 2,000-mile border. India has control over the Dalai Lama's movements, both within India and abroad.
But as relations with China have deteriorated to historic lows over the past year due to deadly border aggression, there has been increased pressure on the Indian government to strengthen its Tibet policy in order to counter China, including declaring that only the Dalai Lama can choose his successor. Last month, in what was described as a "significant departure" from previous policy, Indian prime minister Narendra Modi wished the Dalai Lama happy birthday on Twitter and, according to the president of the Tibetan parliament-in-exile, a meeting is planned between the two this year.
The controversies over the Dalai Lama's successor are likely to have a direct impact on India; one possible scenario put forward by the Dalai Lama himself is that he could be reincarnated in a "free country", likely to be India rather than Tibet.
Last week, it emerged that several members of the Dalai Lama's inner circle, as well as senior figures in the Tibetan Central Administration, which operates out of Dharamshala, were among those selected as potential targets for surveillance with Pegasus spyware made by NSO group. Analysis suggests it was the Indian government selecting the potential surveillance targets. The Indian government denies any surveillance.
India is not alone in seeing the Dalai Lama's succession as a matter of geopolitical importance. Last year, in a direct shot at China, the US revised its Tibet policy to declare that only Tibetans had the right to select the next Dalai Lama.
According to teachings, each Dalai Lama is a reincarnation of the Avalokiteśvara, who embodies the compassion of all Buddhas. He is both the foremost spiritual leader of the Gelug school of Tibetan Buddhism and in many times past and present also a political leader of the Tibetans.
Traditionally, after he dies, a search begins in Tibet to find his reincarnation, based on signs such as where he was looking when died, which direction the smoke blows when he is cremated and visions interpreted from Lhamo La-tso, an oracle lake in Tibet. Based on these visions, search parties are sent out to find children born around the date of his death who match these visions and are then put through a series of tests, until the right one is divined. While most Dalai Lamas have been found in Tibet, one was born in Mongolia and another in an area that is now India.
But with Tibet under the control of China, this process which led to the discovery of two-year-old Lhamo Dhondup – now known as Tenzin Gyatso, the 14th Dalai Lama – in a small farming village in north-eastern Tibet in February 1940, is unlikely to be repeated. It is now enshrined in law that the Chinese government must approve all reincarnations of senior Buddhist Lamas (teachers), including the Dalai Lama, a position that was strongly reiterated in a Tibet white paper released by China in May this year, on the 70th anniversary of its annexation of Tibet.
This has been rejected by the Dalai Lama and the Tibetan parliament in exile, which sits in Dharamshala. Penpa Tsering is the president of the parliament-in-exile, and works closely with the Dalai Lama. He said: "A non-believer, atheist government like China interfering in Tibetan spiritual matters is a complete no-no, it cannot be accepted. The world has turned against China. We firmly believe no one will trust their choice."
The Dalai Lama has also expressed concern that his reincarnation will be hijacked and politicised in "brazen meddling" by the Chinese, and has publicly contemplated being reincarnated as a woman or not at all.
The Dalai Lama has put forward three options for his reincarnation, all a departure from the past. The first is that he will be reincarnated in the traditional form, reborn as a child, but outside Tibet. The other options invoked even more niche Buddhist ideas of "emanation" and opened up the possibility of the Dalai Lama appointing a living successor before he dies. He has rejected the legitimacy of the Chinese government's proposed method of finding his reincarnation, which involves a name being pulled from a "golden urn".
While the Dalai Lama was once spiritual leader only to Tibetans, he now has a huge following and has become something of a global celebrity. Attempts by China to interfere in his reincarnation would be likely to spark a global backlash.
For the Tibetan leadership, the issue is not seen as pressing; aside from a brief cancer scare, the Dalai Lama is reported to be in good health and has himself said he will begin making a decision about his reincarnation options after he turns 90.
"His Holiness the Dalai Lama has said many times in jest that if the Chinese are really concerned about the issue of reincarnation, they should look for Mao Zedong's reincarnation first, Deng Xiaoping's second [both deceased Chinese communist leaders], and then maybe the Dalai Lama," said Tsering.
While officially there has been no communication between the Chinese and the Tibetans since 2010, Tsering confirmed that the back channels between the two sides remained active, and that the Tibetan leadership and the Dalai Lama were now pushing for the Dalai Lama to finally be allowed to visit Tibet and China for the first time since he escaped.
But Tsering emphasised that the issue of the next Dalai Lama was not up for negotiation with the Chinese government. "Reincarnation is a decision that has to be made by the person who's going to be reincarnated. So we would advise the Chinese leadership to learn Buddhism first," he said.
However, the Chinese government is already preparing the groundwork for selection of the next Dalai Lama. According to Barnett, the Chinese Communist party in January secretly assembled 25 senior government figures into a committee to begin preparing for the selection process. "We also know from personal accounts that the Chinese have spent the last 10 years winning over individual Lamas inside Tibet, offering them free trips to China and telling them that if they support Beijing they won't be persecuted, so that when the time comes these Lamas will support the Chinese choice for the Dalai Lama," said Barnett. "It's proving very effective."
The preparations appear to be a Chinese attemp tto avoid repeating the chaotic events of 1995, when, without consulting the Chinese government, the Dalai Lama declared that a six-year-old boy, Gedhun Choekyi Nyima, was the next reincarnated Panchen Lama, the second most important figure in Tibetan Buddhism. Three days later, Nyima disappeared and has not been seen since. The Panchen Lama that the Chinese government then appointed in his place remains rejected by most Tibetans.
The Chinese government's apparent determination to select and control the next Dalai Lama is also seen as a response to the enduring popularity of the current spiritual leader, which has undermined their control of Tibet. Despite extensive "re-education" and propaganda programmes and the banning of any image of the Dalai Lama inside Tibet, he is still secretly revered by many Tibetans.
The Chinese government has repeatedly accused the Dalai Lama of "separatist" activities and held him responsible for the self-immolations that Tibetans still carry out in protest, and Tibetan uprisings such as those in 2008."The fact that the Chinese government wants a reincarnation of their choice shows they consider the institution important enough that it needs to be owned and manipulated in order to finally settle to Tibet issue," said Amitabh Mathur, a former adviser to the Indian government on Tibetan affairs. "This is largely due to the exceptional personality of the 14th Dalai Lama and the hold he still has over Tibetans. Hence the desperation to have their own Dalai Lama."
https://www.theguardian.com/world/2021/jul/31/tibet-and-china-clash-over-next-reincarnation-of-the-dalai-lama#:~:text=According%20to%20teachings%2C%20each%20Dalai,political%20leader%20of%20the%20Tibetans.
Previous Avalokiteśvara – compassion of all Buddhas
Next FREE TIBET

redpajama_set_name: RedPajamaCommonCrawl


text:
Home US News The Catastrophe Caused by Trump Supporters on Wednesday further Strengthens Biden's Administration
The Catastrophe Caused by Trump Supporters on Wednesday further Strengthens Biden's Administration
Trump supporters have made yet another move to put his legacy into jeopardy. In November 2020 presidential elections, Democrat Presidential candidate Joe Biden emerged victoriously. On this clear-cut win, Trump and his supporters accused the Democrats of rigging the election.
In the wake of his loss, Trump refused to leave the office at first, but now he has decided to carry forward the transition process. As the date for transition draws near, Trump fans stormed the US Capital, a move that led to chaos and mayhem in the capital.
It has not only put Trump's efforts into danger, but it has bruised the image of the Republican Party as well. However, at the end of the day, whatever happened in the Capitol on Wednesday was the result of constant gaslighting by Trump through his tweets.
By winning Georgia's runoff elections, Democrats were already a step further, and this act of hooliganism has given them more power. Democrats can now nullify all of Trump's recent executive orders. Moreover, Wednesday's incident has given a reason to diffuse all of Trump's efforts without any intervention.
Georgia's loss could also mean an end of Trump's political career, as the footages of the Capital break-in will be played on the loop to remind Americans about the catastrophe and unrest that pro-Trump protestors caused in the Capital.
Nonetheless, there can be no justification to break in and cause unrest and chaos in the city. It was very childish for the Trump protestors to trespass and fight with the police and beat innocent natives of the city.
During the last year, BLM- Antifa ignited protests were condemned, and they were also charged for their deeds.
Other than America, Trump has also lost one of his most loyal ally in, Mike Pence. According to the reports, there was a call from protestors to arrest the Vice President, as he was not able to fulfill Trump's agenda to revoke the results of the elections.
All in all, with chaos and uncertainty still prevailing in the capital, it can be easily said that Trump has let the American people down with his uncalled-for actions.
Previous articleCan the 25th Amendment be invoked in the Wake of the Capitol Siege?
Next articleUS Economy Suffers Loss of Jobs: Hotel industry worst hit


text:
Reign of athena
roa2020
Album Released (finally)
by roa2020	on May 13, 2021 May 13, 2021
As of May 10, 2021 Reign of Athena's first full length album was released to the masses. It is 11 hard driving tunes for your listening pleasure. The album has been released on all major streaming platforms like iTunes, Amazon, Pandora and Spotify as well as YouTube. You can purchase the digital download of the album NOW on reignofathena.com/shop
Reign of Athena Begins.
by roa2020	on June 17, 2020 June 18, 2020
In September 2019 Reign of Athena was formed. At the time the band consisted of Kristine Scream on vocals, Andy Hall on drums and Adam Long on guitar. Shortly after the band picked up guitarist Jeff Eller and bassist Kurt Marlette.
Over the course of the first few months some changes were made and the musical direction was changed to a slightly heavier direction. With that, the band picked up guitarist Brian Witt to replace Jeff Eller and Reign of Athena began to pick up pace.
Over the course of 9 months the band created a 10 songs for their first album, has released 4 singles, been featured on 95.5 Pure Rock out of Cincinnati, OH and has 2 more recording dates and many more releases to come.
Into the Den Single Released and Streaming.
The song, Into the Den, expresses the effects that drugs and abuse can have on a person and how easily it is to fall deep and hit rock bottom.
This song is just one installment out of 10 from the upcoming album, Fog of War; the album dives into drugs, fake friendships, stealing and lies and what it takes to remove yourself from that life. The song speaks on the difficulties you must face and the process of realization you must go through to bring yourself out of that lifestyle.
Into the Den has been released for free download and is now available on Pandora, Spotify and YouTube.
Featured Band on 96 Pure Rock.
Reign of Athena isn't even a year old. Not a live show has been played, but the music is doing all the work. The radio station Pure Rock 96 out of Cincinnati featured the bands 4th single release, Fight or Flight all week for the beginning of June. The band will continue to push its' music to as many alternative outlets as they can until live performances are possible.


text:
Maissana (Maissann-a in ligure) è un comune italiano di 581 abitanti della provincia della Spezia in Liguria.

Geografia fisica
Il territorio di Maissana è situato nell'alta val di Vara lungo la sponda destra del fiume Vara.

Storia

Secondo studi effettuati sul territorio, il borgo di Maissana e le rispettive frazioni furono abitate molto probabilmente dalla tribù dei Lapicini, popolo dei Liguri localizzato tra i paesi costieri di Moneglia e Sestri Levante ed l'entroterra sestrese, particolarmente abili nell'estrazione e lavorazione della pietra locale (lapis), ardesia e arenaria soprattutto.

Intorno al 205 a.C. fu proclamato municipio dell'Impero romano entrando a far parte della nona regione romana; è di questo periodo storico l'eccezionale ritrovamento di alcune monete romane risalenti, secondo gli studi, dell'epoca imperiale di Claudio e Nerone. Lo storico cinquecentesco Agostino Giustiniani, nella descrizione della Liguria inclusa negli "Annali", pubblicati nel 1537, afferma che per il territorio Maissana passava un ramo dell'antica via Romea che dalla zona costiera di Sestri Levante, e risalendo la val Petronio costeggiando il torrente omonimo passando per l'attuale Castiglione Chiavarese, consentiva il raggiungimento delle odierne località e frazioni del territorio maissanese quali Fasciette, Costa di Salterana, Torza; la strada, dividendosi in due biforcazioni, raggiungeva quindi il parmense e l'Appennino ligure passando per Varese Ligure o ritornava verso ovest e quindi in val Graveglia nel genovese.

In epoca feudale fu dominio degli Estensi e, in seguito, della famiglia Malaspina così come sancì il diploma imperiale di Federico Barbarossa, datato al 29 settembre 1164, anche per altri paesi dell'alta val di Vara. La comunità religiosa della Plebs de Varia, comprendente oltre Maissana anche Varese Ligure, fu invece legata all'arcidiocesi di Genova già dal 1031, a differenza di altri borghi della valle e della costa levantina che, di fatto, furono assoggettati al potere spirituale della diocesi di Brugnato.

La proprietà sul feudo di Maissana passò quindi ai Fieschi, conti di Lavagna, che in località Lagorara edificarono un castello. Il territorio seguì pertanto le sorti della famiglia fliscana fino al 1547 quando, a seguito della celebre congiura di Gianluigi Fieschi, le proprietà passarono nelle mani dei Doria e quindi indirettamente alla Repubblica di Genova. Quest'ultima inglobò il feudo maissanese nella podesteria di Castiglione Chiavarese, all'interno del capitaneato di Chiavari.

Nel 1797 con la dominazione francese di Napoleone Bonaparte rientrò dal 2 dicembre nel Dipartimento dell'Entella, con capoluogo Chiavari, all'interno della Repubblica Ligure. Dal 28 aprile 1798 con i nuovi ordinamenti francesi, Maissana rientrò nel VI cantone, come capoluogo, della Giurisdizione del Gromolo e del Vara e dal 1803 centro principale del VII cantone del Gromolo nella Giurisdizione dell'Entella. Annesso al Primo Impero francese dal 13 giugno 1805 al 1814 venne inserito nel Dipartimento degli Appennini.
Nel 1815 fu inglobato nel Regno di Sardegna, secondo le decisioni del Congresso di Vienna del 1814, che sottopose la municipalità di Maissana nella provincia di Chiavari sotto la divisione di Genova. Dal 1859 al 1923 il territorio fu compreso nel VII mandamento di Varese del circondario di Chiavari dell'allora provincia di Genova, nel Regno d'Italia. Con l'istituzione nel 1923 della provincia della Spezia, fu inglobato in quest'ultima amministrazione provinciale.

Una successiva modifica ai confini comunali si verificò nel 1937 quando, con Legge nº 81 del 18 gennaio, la frazione di Statale passò dall'ente comunale di Maissana all'odierno comune di Ne in provincia di Genova.

A partire dagli anni cinquanta e sessanta del Novecento il comune ha vissuto uno spopolamento sempre più crescente per il trasferimento degli abitanti verso i paesi del primo entroterra e della costa come Sestri Levante, dove le principali occupazioni erano impiegate nei cantieri navali della Fincantieri di Riva Trigoso o della Fabbrica Italiana Tubi sempre nel sestrese; solo più recentemente si sta verificando una sorta di "ripopolamento" degli antichi borghi e nuclei del territorio maissanese.

Dal 1973 al 31 dicembre 2008 ha fatto parte della Comunità montana dell'Alta Val di Vara e, con le nuove disposizioni della Legge Regionale nº 24 del 4 luglio 2008, fino al 2011 della Comunità montana Val di Vara.

Simboli

Lo stemma è stato concesso con il decreto del presidente della Repubblica del 5 luglio 1955.

Monumenti e luoghi d'interesse

Architetture religiose
 Chiesa parrocchiale di San Bartolomeo nel capoluogo di Maissana costruita nel 1582; l'altare maggiore in marmo colorato è del 1771, mentre il campanile è opera del 1754.
 Oratorio di Santa Maria Maddalena nel capoluogo di Maissana. All'interno è conservata una statua lignea policroma, databile al Settecento e di probabile scuola scultorea del Maragliano.
 Santuario Crocetta di Nostra Signora di Montallegro nel capoluogo di Maissana.
 Chiesa parrocchiale di San Lorenzo nella frazione di Campore.
 Oratorio di Santa Caterina d'Alessandria nella frazione di Campore.
 Cappella di San Bernardo nella frazione di Campore.
 Chiesa parrocchiale di San Martino nella frazione di Cembrano.
 Chiesa parrocchiale di San Bartolomeo nella frazione di Chiama; fu l'unica comunità parrocchiale, a differenza degli altri borghi del territorio maissanese soggetto all'arcidiocesi di Genova, ad appartenere alle dipendenze della diocesi di Brugnato.
 Chiesa di Nostra Signora della Visitazione nella frazione di Colli.
 Chiesa parrocchiale di San Pasquale nella frazione di Disconesi.
 Chiesa parrocchiale di San Michele Arcangelo nella frazione di Ossegna.
 Chiesa di Santo Stefano nella frazione di Salterana.
 Chiesa di Santa Maria Assunta nella frazione di Santa Maria di Lagorara. Risalente al 1200, presenta degli affreschi del 1952 eseguiti da Cesare Donati ed è dotata di un organo a canne con trasmissione meccanica, restaurato l'ultima volta nel 1995. Conserva inoltre, nella torre campanaria, il più grande concerto di campane della val di Vara, costituito da 5 bronzi in Do diesis, di cui il peso della sola campana maggiore è di circa 15 quintali.
 Chiesa parrocchiale di San Bartolomeo nella frazione di Tavarone. L'attuale parrocchiale fu edificata nel XVII secolo in sostituzione della preesistente intitolata a San Siro; il coro ligneo è del 1715.
 Chiesa di Nostra Signora del Sacro Cuore nella frazione di Torza.

Siti archeologici

Il sito archeologico di Valle di Lagorara, percorso dal torrente omonimo, è un'area situata a circa 750 m sul livello del mare lungo una fascia tra il rio Lagorara e il versante occidentale del monte Scogliera. I diversi studi e scavi, effettuati tra il 1988 e il 1995 dalla Soprintendenza Archeologica della Liguria, hanno portato alla luce quella che, di fatto, è una miniera di diaspro a cielo aperto e di grandi dimensioni. Sono state localizzate due principali aree di estrazione, oltreché due ricoveri o ripari sul versante opposto rispetto alla zona di estrazione e alcuni reperti come schegge di scarto, frammenti di percussori e vari oggetti in ceramica.

Nei successivi studi, effettuati dopo gli eccezionali ritrovamenti, e monitorati dal dottor Roberto Maggi con l'ausilio del personale del museo archeologico di Chiavari, si è potuto stabilire che il materiale estratto era semilavorato e molto probabilmente destinato ad altri siti per la definitiva lavorazione. Le datazioni radiocarboniche, compiute per i materiali ritrovati, hanno altresì confermato che il sito potrebbe collocarsi in un periodo tra il 3500 a.C. e 2000 a.C.

Nelle frazioni di Cembrano, Ossegna e Santa Maria di La sono presenti strutture di accoglienza adibite alla ricezione dei visitatori del sito e all'organizzazione di laboratori archeologici in favore delle scolaresche che si recano in visita.

Società

Evoluzione demografica

Etnie e minoranze straniere
Secondo i dati Istat al 31 dicembre 2019, i cittadini stranieri residenti a Maissana sono

Geografia antropica

Il comune è costituito, oltre che dal capoluogo Maissana, dalle dieci frazioni di Campore, Cembrano, Chiama, Colli, Disconesi, Ossegna, Salterana, Santa Maria, Tavarone e Torza per un totale di 45,43 km2.

Confina a nord con il comune di Varese Ligure, a sud con Casarza Ligure (GE), Castiglione Chiavarese (GE) e Carro, ad ovest con Varese Ligure, Ne (GE), Casarza Ligure e Castiglione Chiavarese e ad est con Varese Ligure e Carro.

Economia
La principale risorsa economica del comune è l'attività legata all'agricoltura e al turismo agro-alimentare.
Anche le cooperative agricole-boschive rivestono un ruolo importante per l'impiego a livello territoriale, mentre un'altra buona parte degli abitanti trova impiego nel settore dei servizi pubblici e privati del distretto.

Infrastrutture e trasporti

Strade
Il centro di Maissana è attraversato principalmente dalla strada provinciale 54 che nella frazione di Torza si innesta con la strada statale 523 del Colle di Cento Croci, nel tratto tra Castiglione Chiavarese e Varese Ligure.

Mobilità urbana
Da Sestri Levante (GE) un servizio di trasporto pubblico locale gestito dall'AMT garantisce quotidiani collegamenti bus con Maissana e per le altre località del territorio comunale, oltre al collegamento da/per le vicine località di Varese Ligure e San Pietro Vara. I collegamenti da/per Brugnato , Sesta Godano e La Spezia sono assicurati via bus dall'ATC, con capolinea Varese Ligure e San Pietro Vara.

Amministrazione

Il municipio, fino al 2011 situato nella storica sede a Maissana, è stato provvisoriamente trasferito nel "Centro Didattico Espositivo" sito in frazione Cembrano. Nel 2020 sono iniziati i lavori di ristrutturazione della vecchia sede comunale, sita nella frazione capoluogo. La ristrutturazione dell'esterno dell'edificio e la messa in sicurezza risulta ultimata nel 2022. A lavori ultimati è previsto il trasferimento degli uffici comunali presso la storica sede principale.

Note

Voci correlate
 Liguria
 Provincia della Spezia
 Val di Vara

Altri progetti

Collegamenti esterni

redpajama_set_name: RedPajamaWikipedia


SanDisk's 400GB SanDisk Ultra is on sale for only $84 on Amazon today.
Boosting your storage is always a good idea, and today, gobbling up a lot of gigabytes doesn't have to be expensive. You can grab the 400GB SanDisk Ultra microSDXC card for just $83.98 on Amazon, down from a list price of $250 and a crazy low price for such a substantial amount of storage.
This card will bring a whole lot more space to your Android device, PC, or even your Nintendo Switch on the cheap. With transfer speeds up to 100MB/s, you'll be able to move up to 1,200 photos in a minute, and the connected SanDisk Memory Zone app helps you view and move files even easier. This microSD card is designed to help speed up app launch speeds and performance, too.
While we haven't tried this memory card ourselves, it's a hit on Amazon, with 4.5 stars out of 5 across nearly 12,000 user reviews.


Even the most remote place in the world, Antarctica, has reached 400 ppm of carbon in the atmosphere.
Rock Against the TPP is a nationwide concert tour to stop the biggest corporate power grab in history, the Trans-Pacific Partnership.
Believe it or not, some 80,000 chemicals on the market have never been tested for their impact on human health.
90,000 people want a fracking ban included in the Democratic National Platform.
Knock, Knock, Are You Aware the US Can Run on 100% Renewable Energy?
This summer, people will knock on doors in 19 states to let them know this isn't a pipe dream.
Congress is expected to vote on the Trans-Pacific Partnership after the November elections.
Pledges range from doubling clean energy R&D to developing super-efficient air conditioners.
By 2020, homeowners will own the majority of solar systems.


Join the Weight Loss Challenge, a 12-week course to gain the knowledge and confidence, to achieve healthy lasting weight loss, well beyond these 12 weeks.
•	WANT TO GET FIT AND FEEL HEALTHY? •	WANT TO LOSE WEIGHT AND FEEL GREAT ABOUT YOUR BODY? •	WANT TO INCREASE YOUR STRENGTH AND STAMINA?
How to become a monthly or yearly link on this site.


text:
Evening Links for January 10th
By Zester	— 1 week ago
https://www.taipeitimes.com/News/world/archives/2022/01/11/2003771158
https://www.theepochtimes.com/t-cells-from-common-colds-cross-protect-against-infection-with-covid-19-study_4203409.html
https://www.theguardian.com/world/2022/jan/10/venezuelan-opposition-defeats-maduro-candidate-hugo-chavez-home-state-barinas
https://www.thegatewaypundit.com/2022/01/new-mexico-democrat-governor-grisham-accused-serial-law-breaking-former-space-company-ceo/
https://trendingpolitics.com/there-is-a-hilarious-update-on-aocs-vacation-to-mandate-free-florida-knab/
https://odysee.com/@ProjectVeritas:7/tomorrow-8pm-exposefauci:1
https://www.nytimes.com/live/2022/01/10/world/russia-us-ukraine-talks
https://www.reuters.com/world/asia-pacific/iran-calls-release-afghan-funds-during-taliban-envoys-visit-2022-01-10/
https://www.devdiscourse.com/article/business/1876766-sri-lankas-president-asks-china-to-restructure-debt-repayments
https://www.theepochtimes.com/california-says-covid-positive-health-workers-can-get-back-to-work-amid-shortages_4201840.html
https://www.theepochtimes.com/supreme-court-justice-sotomayor-fact-checked-over-false-covid-19-claim_4201871.html
https://www.zerohedge.com/economics/fed-vice-chair-clarida-abandons-ship-two-weeks-early
https://www.theepochtimes.com/most-covid-19-patients-in-new-jersey-hospitalized-admitted-for-non-covid-reasons-officials_4204097.html
Daily links for July 7th
https://www.forbes.com/sites/adamandrzejewski/2021/07/01/bidens-white-house-payroll-is-most-expensive-in-american-history/
https://nypost.com/2021/07/04/hunter-biden-engaged-in-some-daddy-pay-care-devine/
https://dailyexpose.co.uk/2021/06/12/official-data-shows-more-people-have-died-because-of-the-covid-vaccines-in-6-months-than-people-who-have-died-of-covid-19-in-15-months/
https://interestingengineering.com/pfizer-vaccine-sees-a-drop-in-protection-against-infections-in-israel
https://www.dailyveracity.com/2021/07/05/almost-half-of-residents-want-out-of-san-francisco-as-retail-chains-flee-and-progressive-crime-policies-take-over/
https://www.zerohedge.com/markets/zoltan-sees-reverse-repo-hitting-2-trillion-weeks-what-happens-then
https://news.yahoo.com/newborn-among-19-missing-kids-232458673.html
https://www.theepochtimes.com/dr-bret-weinstein-perverse-incentives-in-the-vaccine-rollout-and-the-censorship-of-science_3885796.html
https://www.theepochtimes.com/mkt_breakingnews/us-soccer-responds-to-claims-that-womens-team-disrespected-vet-during-national-anthem_3888808.html
https://www.theautomaticearth.com/2021/07/the-great-big-delta-scare/
https://www.theverge.com/2014/6/23/5835326/nestle-wants-to-make-a-real-star-trek-food-replicator
https://www.oann.com/china-to-move-in-on-afghanistan-after-u-s-troop-removal/
https://degraw.substack.com/p/joe-rogan-and-dr-joseph-varon-ignite
https://crimeofthecentury2020.com/the-maricopa-audit-separating-fact-from-fiction
https://resistthemainstream.org/top-u-s-general-in-afghanistan-responds-to-bidens-withdrawal/
https://youtu.be/UvJKf2Mmr7s North Korean defector has bold challenge for Democrats bashing America
https://www.reuters.com/world/middle-east/iran-informs-iaea-plans-produce-enriched-uranium-2021-07-06/
https://www.wsj.com/articles/nixon-warned-about-u-s-decline-11625585964?mod=opinion_lead_pos10
https://conservativebrief.com/calls-for-all-counties-44450/
https://youtu.be/dYCXMaB1Y7c Haitian President assassinated
Daily Links for December 15th
By Zester	—	1 month ago
https://thenationalpulse.com/exclusive/private-fauci-zuckerberg-emails-offering-data-reports/
https://www.zerohedge.com/markets/stocks-bond-commodities-crumble-dollar-rips-ahead-fed
https://www.zerohedge.com/markets/goldman-rings-alarm-collapsing-market-breadth-51-all-market-gains-april-are-just-5-stocks
https://www.prnewswire.com/news-releases/ibm-and-samsung-unveil-semiconductor-breakthrough-that-defies-conventional-design-301443823.html
https://100percentfedup.com/kroger-bans-unvaccinated-employees-yesterdays-heroes-from-receiving-sick-pay-if-they-get-covid-will-also-add-monthly-insurance-surcharge/
https://www.washingtonexaminer.com/policy/defense-national-security/iran-demands-total-sanctions-removal-as-last-chance-nuclear-talks-falter
https://youtu.be/lk6lkW4A7Ec The Unemployed and semi-unemployed might reach 300-400M people/Newly unemployed in 7 industries
https://www.telegraph.co.uk/news/2021/12/15/wuhan-lab-leak-now-likely-origin-covid-mps-told/
https://www.zimeye.net/2021/12/14/mangudya-clears-air-on-zim-currency/
https://www.bloombergquint.com/china/china-developers-sink-as-shimao-deal-stokes-governance-concern
https://www.theepochtimes.com/mkt_morningbrief/taiwanese-lab-leak-sharpens-debate-on-pandemic-origin_4157452.html
https://www.lewrockwell.com/2021/12/joseph-mercola/outpatient-treatments-for-covid-19-reviewed/
Daily Links for November 5th with Mr C
https://www.youtube.com/watch?v=mLkbW3lObLk Wow | Brazil | No Green pass
https://support.google.com/youtube/answer/9891785 YouTube policy
https://rumble.com/voqdjb-bodycam-footage-of-democrat-virginia-delegate-chris-hurst.html
https://youtu.be/14oCSp2HhIg Rep. Cammack's Facebook Live Slamming Pelosi & Biden For Build Back Broke Socialist Spending Spree
https://youtu.be/pAMCIPglBW4 Monkey Werx Global Food and Energy Shortages
https://youtu.be/tG8gRoaCczQ Thought Elections Couldn't Sink Any Lower?? THINK AGAIN!!!
https://youtu.be/sfvK-9xra1o Noem Announces South Dakota Joining Lawsuit Against Biden's OSHA Vaccine Mandate
https://nypost.com/2021/11/04/activists-swarm-manchins-maserati-in-dc-garage/
https://thefederalist.com/2021/11/04/audit-wisconsin-could-have-counted-enough-illegal-votes-to-tip-the-2020-election-to-biden/
https://www.foxnews.com/media/abc-cbs-nbc-igor-danchenko-durham-probe
https://beckernews.com/dem-governor-signs-executive-order-to-turn-away-unvaccinated-from-hospitals-and-prioritize-treatment-to-vaccinated-patients-42917/
https://nypost.com/2021/11/04/dems-war-on-suburban-women-includes-inflation-fueling-spending/


text: PEOPLE & COMPANY NEWS Robert Hawn has joined the West Gulf Maritime Association as Director of Maritime Affairs. Hawn is a veteran of the maritime industry and brings ex- tensive knowledge and a wealth of man- agement experience from within the agency sector. Mr. Hawn is currently the General Manager at Inchcape Ship- ping Services in Houston. Hawn will re- place the recently retired Niels Lyngso. Margaret Kaigh Doyle of the Unit- ed State Maritime Research Center (USMRC) has been named the U.S. vice chairperson of the Training and Competency Working Group for the Society for Gas as a Marine Fuel (SGMF). The organization, whose mission is to promote safety and in- dustry best practices in the use of gas as a marine fuel, is expanding its scope into the United States. The work- ing group will focus on developing a training and competency framework designed to satisfy both IMO and U.S. Coast Guard regulations. Doyle is also a member of the U.S. Coast Guard Chemical Transportation Ad- visory Committee (CTAC). Bobby Dugas has been named gen-eral service manager at Laborde Prod- ucts. Dugas has more than 25 years of experience in the engine service business. Most recently, he held the position of general manager of after-market services at Reagan Power & Compression. Dugas will be respon- sible for service support operations at all three Laborde locations, as well as the company?s network of over 90 ser- vice dealers. Benedict P. Capuco has been ap-pointed Chief Naval Architect at Gibbs & Cox. In this role, Capuco will provide corporate leadership to the company?s naval architecture and marine engineering capabilities and solutions across the Gibbs & Cox global portfolio. Prior to this ap- pointment, Capuco served as Vice President and Group Manager of the Platform Solutions Group of Gibbs & Cox. Capuco holds a bachelor?s of science in Naval Architecture and Ma- rine Engineering from the University of Michigan and a master?s of science in Civil and Ocean Engineering from Johns Hopkins University. Goltens Worldwide has opened a new full service facility in Houston, TX. Leading the operation as General Manager for Goltens is industry vet- eran Mark Evans . Evans is a seasoned maritime executive with over 20 years of experience supporting the marine services industry, working in progres- sively higher technical management and executive positions within Wärtsilä and most recently Rolls-Royce Marine. Maurice Lara has joined the Florida of ces of Glander International Bun- kering as Bunker & Lubricant Broker/ Trader. Maurice Lara brings 8 years of bunkering experience to Glander International Bunkering. He is spe- cialized in supplying throughout the Americas, including the USA, Can-ada, Central and South America and the Caribbean. Lara holds a Bachelor of Science in Business Administration, a minor in Philosophy, is pro cient in English, Spanish and has a good un- derstanding of Portuguese. Chad Appleby has been named Vice President, Tax for The Safariland Group. Appleby will lead the global tax strategy and tax operations of the Company. Appleby is a certi ed pub- lic accountant with more than 15 years of experience working on a wide range of domestic and international tax matters. Appleby joins the Com- pany after spending the last nine years leading the tax department as the Senior Director, Income Tax at PSS World Medical, Inc. Appleby received his BBA in Accounting from the Uni- versity of Wisconsin and his Masters in Taxation from the University of Denver Graduate Tax Program. The Chamber of Marine Com- merce has named RADM Michael Parks, USCG (Ret.), as Special Advi- sor. In his new role, RADM Parks will work with the Chamber to promote the distinct economic, environmental and safety advantages of the bi-national Great Lakes-St. Lawrence shipping in- DugasHawnEvansCapucoDoyleLaraDecember 201450 MNMN Dec14 Layout 50-59.indd 50MN Dec14 Layout 50-59.indd 5011/24/2014 3:53:52 PM11/24/2014 3:53:52 PM


text:
Drzonowo (deutsch Drenow) ist ein Dorf in der Woiwodschaft Westpommern in Polen. Es liegt in der Gmina Kołobrzeg (Landgemeinde Kolberg) im Powiat Kołobrzeski (Kolberger Kreis).

Geographische Lage
Das Dorf liegt in Hinterpommern, etwa 95 km nordöstlich von Stettin und etwa 12 km südwestlich von Kolberg.

Der nächste Nachbarort ist Zarben etwa ½ Kilometer westlich, auf der anderen Seite eines durch den Kreiherbach gebildeten Wiesentals.

Geschichte
Das Dorf wurde im Mittelalter im Herzogtum Pommern im Rahmen der Deutschen Ostsiedlung in der Form eines Angerdorfes angelegt. Das Dorf wurde erstmals, bereits unter dem Ortsnamen "Drenow", in einer Urkunde aus dem Jahre 1276 genannt, mit der der Camminer Bischof Hermann von Gleichen die Ausstattung des Kolberger Domkapitels regelte. Dem Domkapitel stand der Zehnte aus Drenow zu. Ebenfalls 1276 wurde der Kreiherbach westlich von Drenow als Westgrenze des weltlichen Herrschaftsgebiets der Camminer Bischöfe festgelegt.

Drenow war ein altes Lehen der adligen Familie Manteuffel, in deren Besitz es erstmals 1315 genannt ist. In der pommerschen Hufenmatrikel von 1628 erschien Drenow dann aber, ebenso wie das benachbarte Zarben, im herzoglichen Besitz unter den Dörfern des Amtes Treptow. Auf der Großen Lubinschen Karte des Herzogtums Pommern von 1618 ist "Drenow" eingetragen.

Im Jahre 1666 war Lorenz Christoph von Somnitz, Kanzler von Hinterpommern, Besitzer von Drenow. Dessen Nachkommen besaßen Drenow bis 1748, als Mathias Döring von Somnitz Drenow verkaufte.

Ab 1772 wurden im Gebiet des Gutes verschiedene Verbesserungen durchgeführt, für die König Friedrich II. finanzielle Unterstützung gewährte. Hierzu gehörte die Anlage einer neuen Siedlung im östlichen Bereich der Gemarkung Drenow. Diese Siedlung erhielt den Namen Charlottenhof nach einer Tochter des damaligen Gutsbesitzers.

In Ludwig Wilhelm Brüggemanns Ausführlicher Beschreibung des gegenwärtigen Zustandes des Königlich Preußischen Herzogtums Vor- und Hinterpommern (1784) ist Drenow unter den adeligen Gütern des Fürstentums Cammin aufgeführt. In Drenow gab es damals ein Vorwerk, also den Gutsbetrieb, eine Wassermühle, eine Schäferei, elf Bauern, einen Halbbauern, zwei Kossäten und eine Schmiede, insgesamt 33 Haushaltungen ("Feuerstellen"). Die genannte Wassermühle war die Neumühl am Kreiherbach, die Mathias Döring von Somnitz bereits 1747 verkauft hatte.

Ende des 18. Jahrhunderts wurde ein Vorwerk namens Hanshausen angelegt, das aber letztmals 1864 genannt ist und dann aufgegeben wurde. In der Mitte des 19. Jahrhunderts wurde westlich von Charlottenhof das Vorwerk Sophienhof angelegt.

Im Rahmen der Separation wurde der größere Teil des Landes dem Gutsbetrieb zugeordnet, der kleinere Teil den bäuerlichen Betrieben. Der Gutsbetrieb umfasste im Jahre 1870, als das Gut einem Oberamtmann Peterssen gehörte, 671 Hektar Land. Um 1910 verkaufte der damalige Gutsbesitzer etwa die Hälfte des Landes, das an verschiedene Käufer in Drenow und im benachbarten Naugard ging. Dabei wurde auch das Vorwerk Sophienhof aufgeteilt und es entstanden mehrere neue Hofstellen.

Im 19. Jahrhundert bestanden der Gutsbezirk Drenow und die Landgemeinde Drenow nebeneinander. Der Gutsbezirk Drenow umfasste (Stand 1864) eine Fläche von 688 Hektar und zählte (Stand 1867) 139 Einwohner. Die Landgemeinde Drenow umfasste (Stand 1864) eine Fläche von 620 Hektar und zählte (Stand 1867) 589 Einwohner. Nach der teilweise Aufsiedlung des Gutes wurde der Gutsbezirk nach 1910 in die Landgemeinde Drenow eingemeindet.

Bis 1945 gehörte die Landgemeinde Drenow mit ihren Wohnplätzen Neumühl, Charlottenhof und Sophienhof zum Landkreis Kolberg-Körlin in der preußischen Provinz Pommern.Gemeinde Drenow im Informationssystem Pommern.

1945 kam Drenow, wie ganz Hinterpommern, an Polen. Die Bevölkerung wurde vertrieben und durch Polen ersetzt. Der Ortsname wurde zu "Drzonowo" polonisiert. Heute gehört der Ort zur Gmina Kołobrzeg (Landgemeinde Kolberg).

Entwicklung der Einwohnerzahlen
 1816: 242
 1864: 695
 1871: 702
 1905: 651
 1919: 644
 1933: 573
 1939: 529

Siehe auch
 Liste der Orte in der Provinz Pommern

Literatur
 Manfred Vollack: Das Kolberger Land. Seine Städte und Dörfer. Ein pommersches Heimatbuch. Husum Druck- und Verlagsgesellschaft, Husum 1999, ISBN 3-88042-784-4, S. 167–175.

Weblinks

 Drenow beim Verein Kolberger Lande

Fußnoten

Ort der Woiwodschaft Westpommern
Ort in Pommern
Gmina Kołobrzeg
Ersterwähnung 1276


Controls Fire Ants, Cinch Bugs, Mole Crickets and Ticks when applied in and around Telecommunications, Power, Utilities and Railroad Systems Equipment.
Controls a wide range of insects including fire ants. Produces predictable results.
Very effective on insects in the soil. Ideal for fire ant control.
Has low water solubility. Lasts longer in soil.
Non-corrosive and non-conductive. May be used in a variety of locations.
Individual application packages or 4 lb. shaker can. No measuring needed, convenient storage.