text:
\section{Homfly Polynomial and Some Caluculations}
\subsection{Relation to Homfly Polynomial}
In this section, we shall discuss the relation between Theorem \ref{th:mainresult} and Homfly polynomial.
\begin{definition}\hspace{-5pt}{\bf.}\hspace{6pt}(Homfly polynomial)
For a link diagram $L$, the Homfly polynomial $P_L(t,z)$ is characterized by the skein relation:
\begin{eqnarray*}
 tP_{L_+}(t,z)-t^{-1}P_{L_-}(t,z)=zP_{L_0}(t,z)
\end{eqnarray*}
\begin{eqnarray}\label{eqn:skein relation}
 P_U&=&1,
\end{eqnarray}
where $U$ denotes a trivial knot. The links $L_+,L_-,L_0$ are given in Figure
\ref{fig:skeinrelation}. $\square$
\begin{figure}[htbp]
\begin{eqnarray*}
  \picfn~~~~\picfo~~~~\picfm
\end{eqnarray*}
    \caption{skein relation}
	\label{fig:skeinrelation}
\end{figure}
\end{definition}

It is known that the Kontsevich integral and the weight system of $su(N)$ gives the
Homfly polynomial. More precisely, the following fact holds.
\begin{fact}\hspace{-5pt}{\bf.}\hspace{6pt}\label{fact:Homfly}
Let $\LL=\{\K_1,\cdots,\K_n\}$ be a link.
Define $\hat{P}_{\LL}(x,N)$ by
  \begin{eqnarray}\label{eq:Homfly}
    \hat{P}_{\LL}(x,N)=N^{n-1}\exp\Bigl(-x\frac{N^2-1}{2N}
    w(\LL)\Bigr)~
    \frac{\hat{Z}_W(\LL)}{\hat{Z}_W(U)},
  \end{eqnarray}
where $w(\LL)$ is given by
\begin{eqnarray*}
  w(\LL)=\sum_{1\le i< j\le n}v_{1}(\{\K_i,\K_j\}).
\end{eqnarray*}
Let $L=\{K_1,\cdots,K_n\}$ be the link diagram of $\LL$. Then,
\begin{eqnarray*}
  P_L(e^{\frac{Nx}{2}},e^{\frac{x}{2}}-e^{-\frac{x}{2}})=\hat{P}_{\LL}(x,N)
\end{eqnarray*}
holds. $\square$
\end{fact}

Since $v_{1},v_{2},v_{3.1},v_{3.2},v_{4.1},v_{4.2},v_{4.3},v_{4.4}$ are link invariants and depend only on its link diagrams, we write $v_{1}(\{K_i,K_j\})$ instead of $v_{1}(\{\K_i,\K_j\})$, etc. From Theorem \ref{th:mainresult} and Fact \ref{fact:Homfly}, we
immediately obtain the following corollary.
\begin{corollary}\hspace{-5pt}{\bf.}\hspace{6pt}\label{co:Homfly}
Up to degree four, the power series expansion of Homfly polynomial with respect to $x$ has the explicit Gauss diagram formula as follows:
\begin{eqnarray}\label{eqn:Homflyformula}
  &&\hspace{-1cm}
  \Bigl[P_L(e^{\frac{Nx}{2}},e^{\frac{x}{2}}-e^{-\frac{x}{2}})\Bigr]^{(4)}
  \nonumber\\
  &&\hspace{-0.5cm}
  =W_{su(N)}^{(4)}\Biggl(N^{n-1}\biggl\{\exp\Bigl(
  \sum_{D\in\bar{\mathfrak{D}}_K}D~u(D:L)
  \Bigr)\biggr\}\biggl\{\sum_{D\in\mathfrak{D}_L}D~w(D:L)
  \biggr\}\Biggr),
\end{eqnarray}
where $W_{su(N)}^{(4)}(D)=\bigl[W_{su(N)}(D)\bigr]^{(4)}$. The first sum
$\displaystyle \sum_{D\in\bar{\mathfrak{D}}_K}$
is taken over the following CC diagrams:
\begin{eqnarray*}
  &&\bar{\mathfrak{D}}_K=\Bigl\{\marua,\marubc,\marudg,\marufa,\marufb\Bigr\}.
\end{eqnarray*}
The second sum $\displaystyle \sum_{D\in\mathfrak{D}_L}$ is taken over the same CC diagrams as (\ref{eq:CC diagrams}). Here $w(D:L)$ is the same as (\ref{eq:w(D,L)}) and $u(D:L)$ is given as follows:
\begin{eqnarray*}
  &&\bullet~~u\Bigl(\marua:L\Bigr)=
  -\sum_{1\le i< j\le n}v_1(\{K_i,K_j\}),\nonumber\\
  &&\bullet~~u\Bigl(\marubc:L\Bigr)=(-\frac{1}{2})\bigl\{\frac{1}{6}+\sum_{i=1}^nv_2  (K_i)\bigr\},\nonumber\\
  &&\bullet~~u\Bigl(\marudg:L\Bigr)=(-\frac{1}{2})^2\sum_{i=1}^n
  v_{3.1}(K_i),\nonumber\\
  &&\bullet~~u\Bigl(\marufa:L\Bigr)=(-\frac{1}{2})^3
  \bigl\{-\frac{1}{360}+\sum_{i=1}^nv_{4.1}(K_i)\bigr\},\nonumber\\
  &&\bullet~~u\Bigl(\marufb:L\Bigr)=\sum_{i=1}^n
  \bigl\{\frac{1}{360}+v_{4.2}(K_i)\bigl\}.\nonumber\\
\end{eqnarray*}
\end{corollary}
\rightline{$\square$}

\subsection{Some caluculations}
We give an example of Theorem \ref{th:mainresult}
(Gauss diagram formula). As an example, we compute $v_{2},v_{3.1},v_{4.1},v_{4.2}$ for a knot diagram $K$ given in Figure \ref{fig:62}.
\begin{figure}[htbp]
	\setlength{\unitlength}{1cm}
\begin{picture}(8,8)(1.5,-1)
\put(3,2.8){\includegraphics{paintg.eps} }
\put(5.3,6){\footnotesize a1}
\put(3.3,6){\footnotesize a2}
\put(3.1,3.8){\footnotesize a3}
\put(4.4,3){\footnotesize a4}
\put(5.5,4){\footnotesize a5}
\put(4.3,5.0){\footnotesize a6}

\put(9,2.8){\includegraphics{painth.eps} }
\put(11.3,6){\footnotesize a1}
\put(9.3,6){\footnotesize a2}
\put(9.1,3.8){\footnotesize a3}
\put(10.4,3){\footnotesize a4}
\put(11.5,4){\footnotesize a5}
\put(10.3,5.0){\footnotesize a6}

\put(4.2,2.2){$K$}
\put(10.2,2.2){$\alpha(K)$}
\put(3,-0.5){\picfd}
\put(9.3,-0.5){\picfe}
\end{picture}
	\caption{the knot diagram $K$, $\alpha(K)$
	and their Gauss diagram $G(K)$, $G(\alpha(K))$}
	\label{fig:62}
\end{figure}
\subsubsection{$v_2(K)$}
Using the Gauss diagram $G(K)$, $G\bigl(\alpha(K)\bigr)$ in Figure \ref{fig:62}, we get
\begin{eqnarray}\label{eqn:example1}
  \hidarii G(K),\marubb\migii_{\chi}=-5,\hspace{1cm}
  \hidarii G(\alpha(K)),\marubb\migii_{\chi}=-1.
\end{eqnarray}
Inserting these into Gauss diagram formula (\ref{eqn:main result2}), we obtain
\begin{eqnarray}\label{eqn:v2-6}
  v_2(K)&=&-\frac{1}{6}+\hidarii \bar{G}(K),\marubb\migii_{\chi} \nonumber\\
  &=&-\frac{1}{6}+\hidarii G(K),\marubb\migii_{\chi}
  -\hidarii G(\alpha(K)),\marubb\migii_{\chi}\nonumber\\
  &=&-\frac{1}{6}-4.
\end{eqnarray}

\noindent{\it Remark.}
Notice that we cannot replace $\alpha(K)$ by a trivial knot $U$ in the second equation of (\ref{eqn:example1}) since $\hidarii G(\alpha(K)),\marubb\migii_{\chi}$ is not a knot invariant.

\subsubsection{$v_{3.1}(K)$}
Using the Gauss diagram $G(K)$ in Figure \ref{fig:62}, we get
\begin{eqnarray}\label{eqn: 6-v31}
\begin{array}{cc}
  \hidarii G(K),\marude\migii_{\chi}=5, &
  \hidarii G(K),\marudd\migii_{\chi}=2, \\
  \hidarii G(K),\marudp\migii_{\chi}=-6. &
\end{array}
\end{eqnarray}
\begin{figure}[tbp]
	\setlength{\unitlength}{1cm}
\begin{picture}(8,4)(1.5,2.5)
\put(6,2.9){\includegraphics{paintn.eps} }
\put(8.3,6.1){\footnotesize a1}
\put(6.3,6.1){\footnotesize a2}
\put(6.2,3.9){\footnotesize a3}
\put(7.4,3.1){\footnotesize a4}
\put(8.4,4.1){\footnotesize a5}
\put(7.3,5.1){\footnotesize a6}

\end{picture}
	\caption{link diagram $Q(\{K:\mbox{a6}\},[\alpha])$}
	\label{fig:6split}
\end{figure}
Next we shall caluculate $I_{3.1}(K)$.
Considering Figure \ref{fig:6split}, we have
\begin{eqnarray*}
  &&\hspace{-0.5cm}R(\{K:\mbox{a}_6\},[\gamma]-[\alpha])\\
  &&
  =~~\Biggl\{\piche\Biggr\}~~-~~\Biggl\{\pichd\Biggr\}~~
  -~~\Biggl\{\pichf\Biggr\}.
  \\
\end{eqnarray*}
We can caluculate the other $R(\{K:\mbox{a}_i\},[\gamma]-[\alpha])$ ($i=1,\cdots,5$) in the same way.
Then we have
\begin{eqnarray*}
  &&\hidarii R(\{K:\mbox{a}_i\},[\gamma]-[\alpha]),\marubb\migii_{\chi}
  =-1~~(i=1,\cdots,5),\\
  &&\hidarii R(\{K:\mbox{a}_6\},[\gamma]-[\alpha]),\marubb\migii_{\chi}
  =0.
\end{eqnarray*}
Inserting these into (\ref{eqn:I31}), we obtain
\begin{eqnarray}\label{eqn:exampleI31}
  I_{3.1}(K)=1.
\end{eqnarray}
Inserting (\ref{eqn: 6-v31}) (\ref{eqn:exampleI31}) into Gauss diagram formula (\ref{eqn:main result31}) yields
\begin{eqnarray}\label{eqn:v31-6}
  v_{3.1}(K)=8.
\end{eqnarray}

\subsubsection{$v_{4.1}(K)$ and $v_{4.2}(K)$}
Using the Gauss diagram $G(K)$,
$G\bigl(\alpha(K)\bigr)$ in Figure \ref{fig:62}, we get
\begin{eqnarray*}
\begin{array}{lll}
  \hidarii \bar{G}(K),\maruga\migii_{\chi}=0, &
  \hidarii \bar{G}(K),\marugb\migii_{\chi}=0, &
  \hidarii \bar{G}(K),\marugc\migii_{\chi}=-6, \\
  \hidarii \bar{G}(K),\marugd\migii_{\chi}=4, &
  \hidarii \bar{G}(K),\maruge\migii_{\chi}=2, &
  \hidarii \bar{G}(K),\marugf\migii_{\chi}=-2, \\
  \hidarii \bar{G}(K),\marubb\migii_{\chi}=-4, &
  \hidarii \bar{G}(K),\marugg\migii_{\chi}=-20, &
  \hidarii \bar{G}(K),\marugh\migii_{\chi}=12, \\
  \hidarii \bar{G}(K),\marugi\migii_{\chi}=0, & & \\
  & & \\
  I_{4.1.1}(K)=4, & I_{4.1.2}(K)=-2, & I_{4.2}(K)=-2.
\end{array}
\end{eqnarray*}
Inserting these equation into Gauss diagram formula (\ref{eqn:main result41}) and (\ref{eqn:main result42}) yields
\begin{eqnarray}\label{eqn:v41-6}
  v_{4.1}(K)=\frac{1}{360}+\frac{34}{3}, ~~~~~~
  v_{4.2}(K)=-\frac{1}{360}+\frac{38}{3}.
\end{eqnarray}
\subsubsection{}
Inserting (\ref{eqn:v2-6}),(\ref{eqn:v31-6}),(\ref{eqn:v41-6}) into the right side of (\ref{eqn:Homflyformula}), we get
\begin{eqnarray}\label{eq:example}
  &&\hspace{-1cm}
  \Bigl\{\mbox{the right side of (\ref{eqn:Homflyformula})}\Bigr\}
  \nonumber\\
  &&
  =1+(N^2-1)x^2+N(N^2-1)x^3
  +\frac{-13+6N^2+7N^4}{12}x^4.
\end{eqnarray}
The Homfly polynomial of $K$ is caluculated by the skein relation
(\ref{eqn:skein relation}):
\begin{eqnarray*}
  P_{K}(t,z)=t^4z^2+t^4-t^2z^4-3t^2z^2-2t^2+z^2+2.
\end{eqnarray*}
We can easiliy check that $\bigl[P_{K}(e^{\frac{Nx}{2}},e^{\frac{x}{2}}-e^{-\frac{x}{2}})]^{(4)}$ coincides with (\ref{eq:example}).

config: arxiv


text:
\begin{document}

\maketitle

\footnotetext{\hskip -.8em   {\em 2010 Mathematics Subject
Classification.}
    {Primary: 35A01. Secondary: 46F05, 46F10.}
    \hfil\break\indent \begin{minipage}[t]{14cm}{\em Key words and phrases:} Euler differential operators, Schwartz distributions, distributions of finite order, global solvability. \end{minipage}.
     \hfil\break\indent

{}}

\begin{abstract}
 Euler operators are partial differential operators of the form $P(\theta)$
where $P$ is a polynomial and $\theta_j = x_j \partial/\partial x_j$. They are surjective
on the space of temperate distributions on $\Rn$. We show that this is, in general, not
true for the space of Schwartz distributions on $\Rn$, $d\ge 3$, for $d=1$, however, it is true.
It is also true for the space of distributions of finite order on $\Rn$ and on certain open
sets $\Om\subset\Rn$, like the euclidian unit ball.

\end{abstract}

Euler partial differential operators are operators of the form $P(\theta)$ where $P$ is a polynomial in $d$ variables and $\theta_j =x_j \partial/\partial x_j$ the Euler derivative. They are partial differential operators with variable coefficients which are singular at the coordinate hyperplanes. In contrary to partial differential operators with constant coefficients they admit distributional zero solutions with compact support, located at the singular locus. On $\CN$ they are surjective onto the annihilator of these zero solutions, in particular they are not surjective but have closed range (see \cite{DL1}). On the space $\cS'(\Rn)$ however they are surjective (see \cite{Vtemp}). The same holds on $\dip$ (see \cite{Vtemp} or Theorem \ref{t3} below). They have dense range in $\Dip$.  This raised the question whether they would be surjective on $\Dip$ for all $d$. In section \ref{s1} we show that this is not true, in general, at least for $d\ge3$. We give examples of differential equation $P(\theta)S=T$ without global solution $S$ even for such a natural operator as $P(\theta)=\sum_{j=1}^d \theta_j^2$.
The reason in this case is not a natural obstruction as in the $C^\infty$-case´, but impossibility to get a solution of locally finite order for some $T$ of infinite, but locally of finite order. In Section \ref{s2} we show that on the space $\cD'_F(\Rn)$ of distributions of finite order every non-trivial Euler differential operator is surjective, that is, every equation $P(\theta)S=T$ admits a global solution. The same holds for the open unit ball in $\Rn$. More general, we give for open $\Om$ conditions for global solvability on $\cD'_F(\Om)$ in terms of $P(\theta)$-convexity and we give conditions, which imply $P(\theta)$- convexity for every non-trivial polynomial $P$.

\section{Preliminaries}
We use the following notation $\partial_j=\partial/\partial x_j$, $\theta_j = x_j\,\partial_j$. For a multiindex $\alpha\in\N_0^d$ we set $\partial^\alpha = \partial_1^{\alpha_1}..\partial_d^{\alpha_d}$, likewise for $\theta^\alpha$. For a polynomial $P(z)=\sum_\alpha c_\alpha z^\alpha$ we consider the  \it Euler operator \rm $P(\theta)=\sum_\alpha c_\alpha \theta^\alpha$ and also the operator $P(\partial)$, defined likewise.

$P(\theta)$ and $P(\partial)$ are connected in the following way.  For $x\in\Rn$ we set
$\Exp(x)=(\exp(x_1),..,\exp(x_d)).$
$\Exp$ is a diffeomorphism from $\Rn$ onto $Q:=]0,+\infty[^d$. Its inverse is $\Log(x)=(\log(x_1),..,\log(x_d))$. The map
$C_\Exp:f\To f\circ\Exp$
is a linear topological isomorphism from $C^\infty(Q)$ onto $C^\infty(\Rn)$. For $f\in C^\infty(Q)$ we have
$P(\partial)(f\circ\Exp)=(P(\theta)f)\circ\Exp$ that is $P(\partial)\circ C_\Exp =C_\Exp\circ P(\theta)$. In this way solvability properties of $P(\theta)$ on $C^\infty(Q)$ can be reduced to solvability properties of $P(\partial)$ on $C^\infty(\Rn)$. This has be done in $\cite{V1}$ and essentially used in \cite{Vtemp}. There it was shown that every non-trivial Euler operator is surjective on $\cS'(\Rn)$, the space of temperate distributions. This result will be used in Section \ref{s2}. We will also make use of the fact that for elliptic $P(\partial)$ distributional zero solutions of $P(\theta)$ on some open $\Om\subset Q$ are real analytic on $\Om$.

Throughout the paper we use standard notation of Functional Analysis, in  particular, of distribution theory, and of the theory of partial differential operators. For unexplained notation we refer to \cite{DK}, \cite{H1}, \cite{MV},

\section{Examples for non-solvability}\label{s1}

We assume $d\ge 2$ and on $\R^{d+1}$ we use the variables $(x,y)$, $x\in\Rn$, $y\in\R$. We consider Euler differential operators  on $\cD'(\R^{d+1})$ and study the solvability of equations $P(\theta)S=T$ where
$$P(\theta)= Q(\theta_1,\dots,\theta_d) + \theta_y^p$$
and
$$T=\sum_{n=0}^\infty f_n(x)\otimes \delta^{(n)}(y).$$
with $f_n\in \Dip$ and $\supp f_n\subset \{x\,:\,|x|\ge n\}$.

We assume that $Q$ and the $f_n$ are chosen in such a way that every solution $F_n$ of $(Q(\theta)+(-n-1)^p) F_n=f_n$ does not vanish on any open subset of the `quadrant' $Q$. We might choose $Q(\theta)=\sum_{j=1}^d \theta_j^2$ and $f_n= \delta_\bn$ where $\bn=(n,\dots,n)$.

If we have such $F_n$ a natural candidate would be $S=\sum_n F_n(x)\otimes \delta^{(n)}(y)$ because
\begin{equation}\label{eq3} P(\theta)(F_n(x)\otimes \delta^{(n)}(y))=((Q(\theta) + (-n-1)^p)F_n(x))\otimes \delta_y^{(n)}.
\end{equation}
However, the series is not locally of finite order, hence does not define a distribution. Anyhow this shows the heart of the problem.

We study the problem on a strip around $\Rn$. We fix a function $\chi\in\cD([-2,+2]$ with $\chi(y)=1$ for $y\in[-1,+1]$ and consider functions $\vp(x,y)\in\cD(\R^{d+1})$ of the form
\begin{equation}\label{eq7}\vp(x,y)=\sum_{n=0}^m \vp_n(x)\chi(y)y^n/n!=\psi(x,y)\chi(y)\end{equation}
with
\begin{equation}\label{eq8}\psi(x,y)=\sum_{n=0}^m \vp_n(x)y^n/n!.\end{equation}
We obtain
$$P(\theta^*)\vp(x,y)=\sum_{n=0}^m (Q(\theta^*)+(-n-1)^p)\vp_n(x)\chi(y)y^n/n!+ (L\psi)(x,y)$$
where $L$ has the form
$$(L\psi)(x,y)= \sum_{j=1}^p(L_j\psi))(x,y)\chi^{(j)}(y).$$
In particular $\supp (L\psi)(x,y)\subset \{(x,y)\,:\,1\le |y| \le 2\}$.

Let now $S$ be a solution of $P(\theta)S=T$. We define $S_n\in\Dip$ by
 $$S_n(\gamma) = S(\gamma(x)\chi(y)y^n/n!).$$
 for $\gamma\in \Di$.

 We obtain
\begin{eqnarray*}
(P(\theta)S)\vp &=& \sum_{n=0}^m S_n((Q(\theta^*)+(-n-1)^p)\vp_n)+S(L\psi)
\\ &=& \sum_{n=0}^m ((Q(\theta)+(-n-1)^p) S_n)\vp_n+S(L\psi)\\
&=& \sum_{n=0}^m (-1)^n f_n(\vp_n).
\end{eqnarray*}
We define $R_n\in\Dip$ by
$$R_n = (-1)^n f_n -(Q(\theta)+(-n-1)^p) S_n)$$
and obtain for $\psi$ like in (\ref{eq8})
\begin{equation}\label{eq5}
\big(\sum_{n=0}^\infty (-1)^n R_n\otimes \delta^{(n)}\big)\psi = R(\psi)
\end{equation}
where
$$R(\psi)=S(L\psi)= \sum_{j=1}^p S((L_j\psi))(x,y)\chi^{(j)}(y)).$$

Both sides of (\ref{eq5}) define distributions in $(\Di\otimes \cE([-2,+2])'$ which coincide on the dense subspace of functions $\psi$ as in (\ref{eq8}), hence they coincide. The left hand side has support in $\Rn\times\{0\}$, while the right hand side has support in $\{(x,y)\,:\,1\le |y|\le 2\}$. So both sides are zero and we have
\begin{equation}\label{eq6}(Q(\theta)+(-n-1)^p)S_n=(-1)^n f_n \end{equation}
for all $n$. Returning to $\vp$ of the form like in (\ref{eq7}) we obtain
\begin{eqnarray*} S\vp &=& \sum_{n=0}^m S_n(\vp_n)= \sum_{n=0}^m S_n(\vp^{(0,n)}(x,0)) = \sum_{n=0}^m (-1)^n (S_n\otimes \delta^{(n)})\vp.
\end{eqnarray*}
So on the dense linear subspace of $\chi(y)\cdot\cD(\R^{d+1})$ consisting of functions $\vp(x,y)$ of the form (\ref{eq7}) we have
$$S = \sum_{n=0}^\infty (-1)^n S_n\otimes \delta^{(n)}$$
which implies that the sum must be locally finite contradicting our assumptions on the solutions of equation (\ref{eq6}). \qed

We have shown:
\begin{proposition}\label{t1} $P(\theta)$ as above is not surjective on $\cD\,'(\R^{d+1})$, $d\ge 2$.
\end{proposition}

This leads to the first main result of this paper.

\begin{theorem}\label{t2} For $d\ge 3$ there are Euler operators which are not surjective on $\Dip$.
\end{theorem}

We have shown non-surjectivity in the following cases.

\begin{example} { \rm For even $p$ and $d\ge 3$ the operator $\sum_{j=1}^d \theta_j^p$ is not surjective in $\Dip$. This holds, in particular for the ``Laplace-Euler''-operator $\sum_{j=1}^d \theta^2$. The same holds for $\sum_{j=1}^{d-1}\theta^2+i\theta_d$ and $\sum_{j=1}^{d-1}\theta^2+\theta_d$, the Euler-operators corresponding to the Schr\"odinger and to the heat equation and also for $\sum_{j=1}^{d-1}\theta_j^2-\theta_d^2$, the analogue to the wave equation. So for $d\ge 3$ we have counterexamples for the classical elliptic, parabolic and hyperbolic polynomials. }
\end{example}

For $d=1$ the situation is different (see the remarks at the end of \cite{Vtemp}).
\begin{theorem}\label{t3} Every non-trivial Euler-operator is surjective in $\dip$.
\end{theorem}

\Proof By the fundamental theorem of algebra it is enough to show it for $\theta-a$, $a\in \C$. For $T\in\dip$ we want to solve $(\theta-a)S=T$.

We set $\cD_0(\R)=\{\vp\in\di\,:\,\vp \text{ flat in } 0\}$. We find $S_0\in\cD_0(\R)'$ such that $x |x|^a S_0'=T_0 := T|_{\cD_0(\R)}$ and put $U_0=|x|^a S_0$. Then
$\theta U_0= a |x|^a S_0 + x |x|^a S_0' = a U_0+T_0$. Therefore $(\theta -a)U_0=T_0$. We extend $U_0$ by the Hahn-Banach theorem to $U\in\Dip$.
Then $\supp (\theta-a)U-T\subset \{0\}$. By \cite{Vtemp} we find $R\in\cS'(\R)$ such that $(\theta - a)R=(\theta-a)U-T$. Then $S=U-R$ solves the problem. \qed

\sc Remark: \rm Let us remark, that our counterexample does not work for $d=1$, that is, in $\cD\,'(\R^2)$. Because in this case the $F_n(x)$ (see the notation at the beginning of this section) can be chosen with support in half-lines beginning with $n$, hence the sum $S=\sum_n F_n(x)\otimes \delta^{(n)}(y)$ is locally finite and defines a distribution.

\section{Solvability in distributions of finite order}\label{s2}

In our examples of differential equations $P(\theta) S= T$ the distribution $T$ always was of infinite order and, of course, locally of finite order. We showed that there cannot exist a solution $S$ locally of finite order. In the proof in \cite{Vtemp}, that for temperate $T$ there is always a temperate solution $S$, one essential feature was that temperate distributions are always of finite order.  We use the result of \cite{Vtemp} to show that for $T$ of finite order there is always a solution $S$ of finite order. Moreover we develop a theory for arbitrary open subsets of $\Rn$. We should remark that the essential difficulty in \cite{Vtemp} was to handle the behaviour in the singular locus of the differential operator, that is, at the union of the coordinate hyperplanes. This was overcome in \cite{Vtemp} and we can use it here to provide local solvability.

From now on $P(\theta)$ is an arbitrary non-trivial Euler operator. $\Om$ and $\om$ denote open subsets of $\Rn$, $\cD_k'(\Om)$ the distributions of Sobolev order $k$ on $\Om$, see below.

We  follow the notation in \cite[\S 14]{MV}. We denote by $H^k$ the Sobolev space of order $k\in\N$. For open $\Om\subset\Rn$ the space $H_0^k(\Om)$ is the closure of $\Do$ in $H^k$. We set $\Hb^{-k}(\Om)=H^k_0(\Om)'$. Every $T\in \Hb^{-k}(\Om)$ can be extended to $\widetilde{T}\in (H^k)'\subset\cS'(\Rn)$. Due to \cite[Theorem 3.5]{Vtemp} and the open mapping theorem, applied to the surjective endomorphism $P(\theta)$ of $\cS'(\Om)$, we obtain:

\begin{lemma}\label{lem1} For every $k\in\N$ there is $m\in\N$ such that for every $\Om$ the following holds: for very $T\in\Hb^{-k}(\Om)$ there is $S\in\Hb^{-m}(\Rn)$ such that $P(\theta)S=T$ on $\Om$.
\end{lemma}

For every $k$ and $m=m_k$ chosen according to Lemma \ref{lem1} we set
$$E(\Om)=\{T\in \Hb^{-m}(\Om)\,:\,P(\theta)T\in \Hb^{-k}(\Om)\}.$$
We obtain an exact sequence
$$0\To N^m(\Om)\stackrel{j}{\To} E(\Om)\stackrel{P(\theta)}{\To} \Hb^{-k}(\Om)\To 0$$
where $N^m(\Om)=\{T\in\Hb^{-m}(\Om)\,:\,P(\theta)T=0\}$ and $j$ is the imbedding. This yields, due to reflexivity:
\begin{equation}\label{eq4}
N^m(\Om)'= E(\Om)'/P(\theta^*)H_0^k(\Om).
\end{equation}
We need some notation.
\begin{definition}\label{d1} For $\Om\subset\Rn$ open $\cD_F'(\Om)$ is the space of distributions of finite order. We set
$$\cD_k'(\Om)=\{T\in\Dop\,:\, T|_\om \subset \Hb^{-k}(\om)\text{ for all open }\om\ssubset\Om\}.$$
\end{definition}
Then we have $\cD_F'(\Om)=\bigcup_{k\in\N} \cD_k'(\Om)$.

\begin{definition}\label{d2}An open set $\Om\subset\Rn$ is called $P(\theta)$ convex if for every $k\in\N$ the following holds: for every $\om_1\ssubset\Om$ there is $\om_2\ssubset\Om$ such that for every $\om\ssubset\Om$ and $\vp\in H_0^k(\om)$ with $P(\theta^*)\vp\in H_0(\om_1)$ we have $\vp\in H_0(\om_2)$.
\end{definition}

Let now a $P(\theta)$-convex open set $\Om\ssubset\Rn$ be given. The we can find an exhaustion $\om_1\ssubset\om_2\ssubset..$ of $\Om$ such that for every $n\in\N$ the sets $\om_n\ssubset\om_{n+1}\ssubset\om_{n+2}$ are in the relation described in Definition \ref{d2}. We obtain a projective spectrum of exact sequences
$$0\To N^m(\om_n)\stackrel{j}{\To} E(\om_n)\stackrel{P(\theta)}{\To} \Hb^{-k}(\om_n)\To 0.$$
From equation (\ref{eq4}) it follows that every $\mu\in N^m(\om_n)'$ which vanishes on $N^m(\om_{n+2})$ also vanishes on $N^m(\om_{n+1})$,
and therefore $N^m(\om_{n+2})|_{\om_n}$ is dense in $N^m(\om_{n+1})|_{\om_n}$ in the topology of $N^m(\om_n)$. Then $P(\theta):\mathcal{E}(\Om)\to \cD_k'(\Om)$ is surjective, where $\mathcal{E}(\Om)=\{T\in\cD_m'(\Om)\,:\, P(\theta)T\in\cD'_k(\Om)\}=\proj_n E(\om_n)$ and, of course, $\cD_k'(\Om)=\proj_n \Hb^{-k}(\om_n)$.

The argument is standard. For the convenience of the reader we give the proof: for every $n$ we find $S_n\in E(\om_n)$ such that $P(\theta)S_n= T|_{\om_n}$. We set $R_1=R_2=0$ and determine inductively $R_n\in N^m(\om_n)$. Let $R_n$ be determined. Then $U_n=S_{n+1}-S_n+R_n \in N^m(\om_n)$ and for $n\ge 2$ we find $R_{n+1}\in N^m(\om_{n+1})$ such that $\|U_n-R_{n+1}\|_{\om_{n-1}}=\|(S_{n+1}-R_{n+1}) -(S_n-R_n)\|_{\om_{n-1}}\le 2^{-n}$. Clearly $S=\lim_n (S_n-R_n)$ exists everywhere on $\Om$ and $P(\theta)S=T$.

We have shown the second main result of this paper:
\begin{theorem}\label{t4} If $\Om\subset\Rn$ is open and $P(\theta)$-convex, then $P(\theta)$ is surjective in $\cD'_F(\Om)$.
\end{theorem}

To get examples of $P(\theta)$-convex sets we need some preparation. We set $Q=]0,+\infty[^d$. For $e\in\{-1,+1\}^d$ we set $Q_e=eQ$. We remark that for any $e$ we have $M_e\circ P(\theta)=P(\theta)\circ M_e$ where $M_e \vp(x)=\vp(ex)$. So the behaviour of $P(\theta)$ on $Q$ determines the behaviour on all `quadrants'.

A set $M\subset Q$ is called {\em m-convex} (cf. \cite{V1}) if $x^t y^{1-t}\in M$ for all $x,y\in M$ and $0<t<1$. $M\subset Q$ is m-convex if and only if $\Log \, M$ is convex. We call it strictly m-convex if $\Log \, M$ is strictly convex. A set $M\subset \NZ$ is called {\em strictly m-convex} if $e (M\cap Q_e)\subset Q$ is strictly m-convex for all $e\in\{-1,+1\}^d$.
 We obtain:

\begin{proposition}\label{p1} If $\Om$ has an exhaustion $\om_1\ssubset\om_2\ssubset\dots$ of open sets such that $\om_n\cap \NZ$ is strictly m-convex with $C^2$-boundary for all $n$, then $\Om$ is $P(\theta)$-convex for all $P(\theta)$.
\end{proposition}

\Proof On test functions $\vp$ we have $P(\theta^*) \vp=P(-1-\theta) \vp=:P^*(\theta)\vp$. Assume that $\vp\in H_0^k(\om_N)$ and $\supp P(\theta^*)\vp\subset \om_n$. Then $\tilde{\vp}:=\vp\circ \Exp$ is a function on $\Log \, (Q\cap \om_N)$ and $\supp P^*(\partial)\tilde{\vp} \subset \Log (Q\cap \om_n)$. By assumption $\Log \, (Q\cap \om_n)$ is strictly convex with $C^2$-boundary. Therefore it is, for any non-trivial $P$, intersection of non-characteristic half-spaces. By Holmgren's theorem (see \cite[Theorem 8.6.8]{H1}), $\supp \tilde{\vp} \subset \Log \,(Q\cap \om_n)$, hence $Q\cap \supp \vp \subset \om_n$. Applying this to $M_e \vp$ for all $e$ we obtain $\supp \vp\cap\NZ\subset \om_n$, hence $\supp \vp\subset \overline{\om}_n\subset \om_{n+1}$. \qed

\sc Remark: \rm The property of the $\om_n$ we really used was, that $\Log (e\,\om_n\cap Q)$ is an intersection of non-characteristic half spaces for all $n$.

Due to the concavity of $\log$ we get:

\begin{lemma}\label{lem2} If $M\subset Q$ is strictly convex and with any $y\in M$ and $x\le y$ (that is $x_j\le y_j$ for all $j$) also $x\in M$, then $M$ is strictly m-convex.
\end{lemma}

From Lemma \ref{lem2}, Proposition \ref{p1}, Theorem \ref{t4} and (for $p=\infty$) the Remark above we get the following examples.

\begin{example} For every non-trivial $P$ the Euler differential operator $P(\theta)$ is surjective on $\cD'_F(\Rn)$ and on $\cD'_F(\Om)$ where $\Om$ is the open unit ball of $\ell_p^d$, ($1\le p \le +\infty$), in particular, the open euclidian unit ball in $\Rn$.
\end{example}


text:
\begin{table}
\caption{Parameters ($\tau_i, \nu_i$) of PDMM. $K$ is the number of blocks randomly chosen from $J$ blocks, and $\tilde{K}_i =\min\{d_i,K\}$ where $d_i$ is the number of nonzero blocks $\bA_{ij}$ in the $i$-th row of $\bA$.}
\centering
\begin{tabular}{|c|c|c|c|}
\hline
$K$  & $\nu_i$ & $\tau_i$ \\
\hline
$K = 1$  & $0$ & $\frac{1}{2J-1}$ \\
\hline
$1< K < J$   & $1 - \frac{1}{\tilde{K}_i}$ & $\frac{K}{\tilde{K}_i(2J - K)}$ \\
\hline
$K=J$ &   $1-\frac{1}{d_i}$ & $\frac{1}{d_i}$ \\
\hline

\end{tabular}
\label{tbl:rpdmm_para}
\end{table}

Consider a direct Jacobi version of ADMM which updates all blocks in parallel:
\begin{align}
 \x_j^{t+1} &= \underset{\x_j\in\cX_j}{\argmin}~ L_{\rho}(\x_j, \x_{k\neq j}^t, \y^{t})~, \label{eq:rpdmm0_x}\\
 \y^{t+1} &=  \y^t + \tau\rho (\bA\x^{t+1} - \a)~. \label{eq:rpdmm0_y}
\end{align}
where $\tau$ is a shrinkage factor for the step size of the dual gradient ascent update. However, empirical results show that it is almost impossible to make the direct Jacobi updates~\myref{eq:rpdmm0_x}-\myref{eq:rpdmm0_y} to converge even when $\tau$ is extremely small.~\cite{luo12:admm,deng14:pmadmm} also noticed that the direct Jacobi updates may not converge.

To address the problem in~\myref{eq:rpdmm0_x} and~\myref{eq:rpdmm0_y}, we propose a backward step on the dual update. Moreover,
instead of updating all blocks, the blocks $\x_j$ will be updated in a parallel randomized block coordinate fashion. We call the algorithm Parallel Direction Method of Multipliers (PDMM).
PDMM first randomly select $K$ blocks denoted by set $\mathbb{I}_t$ at time $t$, then executes the following iterates:
\begin{align}
\x_{j_t}^{t+1} &= \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ L_{\rho}(\x_{j_t}, \x_{k\neq j_t}^t, \hat{\y}^{t}) + \eta_{j_t} B_{\phi_{j_t}}(\x_{j_t}, \x_{j_t}^{t})~, ~j_t \in\mathbb{I}_t, \label{eq:rpdmm_xi} \\
 \y_i^{t+1} &=  \y_i^t + \tau_i\rho ( \bA_i\x^{t+1} - \a_i)~,\label{eq:rpdmm_y}  \\
  \hat{\y}_i^{t+1} & = \y_i^{t+1} - \nu_i\rho (\bA_i\x^{t+1} - \a_i)~, \label{eq:rpdmm_yhat}
\end{align}
where $\tau_i > 0, 0 \leq \nu_i < 1, \eta_{j_t} \geq 0$, and $B_{\phi_{j_t}}(\x_{j_t},\x_{j_t}^t)$ is a Bregman divergence.  Note $\x^{t+1} = (\x_{j_t}^{t+1}, \x_{k\neq j_t}^t)$ in~\myref{eq:rpdmm_y} and~\myref{eq:rpdmm_yhat}. Table~\ref{tbl:rpdmm_para} shows how to choose $\tau_i$ and $\nu_i$ under different number of random blocks $K$ and block sparsity of $\bA$. $K$ is the number of blocks randomly chosen from $J$ blocks, and $\tilde{K}_i =\min\{d_i,K\}$ where $d_i$ is the number of nonzero blocks $\bA_{ij}$ in the $i$-th row of $\bA$.

In the $\x_{j_t}$-update~\myref{eq:rpdmm_xi}, a Bregman divergence is addded so that exact PDMM and its inexact variants can be analyzed in an unified framework~\cite{wang13:badmm}. In particular, if $\eta_{j_t} = 0$,~\myref{eq:rpdmm_xi} is an exact update. If $\eta_{j_t} > 0$, by choosing a suitable Bregman divergence, ~\myref{eq:rpdmm_xi} can be solved by various inexact updates, often yielding a closed-form  for the $\x_{j_t}$ update (see Section~\ref{sec:ipdmm}).

Let $\r^t = \bA\x^t - \a$, then $\r^{t+1}  = \r^t + \sum_{j_t \in \mathbb{I}_t } \bA_{j_t}^c(\x_{j_t}^{t+1} - \x_{j_t}^t)$.
 ~\myref{eq:rpdmm_xi} can be rewritten as
\begin{align}
\x_{j_t}^{t+1} &= \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ f_{j_t}(\x_{j_t}) + \langle \hat{\y}^t, \bA_{j_t}^c\x_{j_t} \rangle + \frac{\rho}{2} \| \bA_{j_t}^c\x_{j_t} + \sum_{j\neq k} \bA_{j_t}^c\x_{j_t}^t - \a \|_2^2 + \eta_{j_t} B_{\phi_{j_t}}(\x, \x_{j_t}^{t})\nonumber \\
& = \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ f_{j_t}(\x_{j_t}) + \langle (\bA_{j_t}^c)^T(\hat{\y}^t + \rho\r^t) , \x_{j_t} \rangle + \frac{\rho}{2} \| \bA_{j_t}^c(\x_{j_t} - \x_{j_t}^t) \|_2^2 + \eta_{j_t} B_{\phi_{j_t}}(\x, \x_{j_t}^{t})~.
\end{align}

Therefore, we have the algorithm of PDMM as in Algorithm~\ref{algo:pdmm}.

\begin{algorithm*}[!tb]
\caption{Parallel Diretion Method of Multipliers}
\label{algo:pdmm}
\begin{algorithmic}[1]
\STATE {\bfseries Input: $\rho, \eta_j, \tau_i, \nu_i$}
\STATE {\bfseries Initialization:} $\x^1,\hat{\y}^1 = \mathbf{0}$
\STATE if $\tau_i, \nu_i$ are not defined, initialize $\tau_i, \nu_i$ as given in Table~\ref{tbl:rpdmm_para}
\STATE $\r^1 = \bA\x^1 - \a = -\a$
\FOR{$t=1 \text{ to } T$}
\STATE randomly pick up $j_t$ block coordinates
\STATE $ \x_{j_t}^{t+1} = \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ f_{j_t}(\x_{j_t}) + \langle (\bA_{j_t}^c)^T(\hat{\y}^t + \rho\r^t) , \x_{j_t} \rangle + \frac{\rho}{2} \| \bA_{j_t}^c(\x_{j_t} - \x_{j_t}^t) \|_2^2 + \eta_{j_t} B_{\phi_{j_t}}(\x, \x_{j_t}^{t})$
\STATE $\r^{t+1} = \r^t + \sum_{j_t \in \mathbb{I}_t } \bA_{j_t}^c(\x_{j_t}^{t+1} - \x_{j_t}^t)$
\STATE $ \y_i^{t+1} =  \y_i^t + \tau_i\rho \r_i^{t+1}$
\STATE $ \hat{\y}_i^{t+1} = \y_i^{t+1} - \nu_i\rho \r_i^{t+1}$
\ENDFOR
\end{algorithmic}
\end{algorithm*}

To better understand PDMM, we discuss the following three aspects which play roles in choosing $\tau_i$ and $\nu_i$: the dual backward step~\myref{eq:rpdmm_yhat}, the sparsity of $\bA$ and the choice of randomized blocks.

\textbf{Dual Backward Step:} We attribute the failure of the Jacobi updates~\myref{eq:rpdmm0_x}-\myref{eq:rpdmm0_y} to the following observation in~\myref{eq:rpdmm0_x}, which can be rewritten as:
\begin{align}\label{eq:rpdmm_x_ep}
\x_j^{t+1}  = \underset{\x_j\in\cX_j}{\argmin} f_j(\x_j) + \langle \y^{t} + \rho(\bA\x^t - \a), \bA_j^c\x_j\rangle + \frac{\rho}{2} \| \bA_j^c(\x_j - \x_j^t) \|_2^2~.
\end{align}
In the primal $\x_j$ update, the quadratic penalty term implicitly adds full gradient ascent step to the dual variable, i.e.,  $\y^t + \rho(\bA\x^t - \a)$, which we call implicit dual ascent. The implicit dual ascent along with the explicit dual ascent~\myref{eq:rpdmm0_y} may lead to too aggressive progress on the dual variable, particularly when the number of blocks is large. Based on this observation, we introduce an intermediate variable $\hat{\y}^{t}$ to replace $\y^t$ in~\myref{eq:rpdmm_x_ep} so that the implicit dual ascent in~\myref{eq:rpdmm_x_ep} makes conservative progress, e.g.,
$\hat{\y}^{t} + \rho(\bA\x^t - \a) = \y^t + (1-\nu)\rho(\bA\x^t - \a)$~,
 where $0 < \nu < 1$. $\hat{\y}^{t}$ is the result of a `backward step' on the dual variable, i.e.,
$\hat{\y}^{t} = \y^t - \nu\rho(\bA\x^t - \a)$.

Moreover, one can show that $\tau$ and $\nu$ have also been implicitly used when using two-block ADMM with splitting variables (sADMM) to solve~\myref{eq:pdmm_K}~\cite{pari14:prox,luo13:padmm}. Section~\ref{sec:connect} shows sADMM is a special case of PDMM. The connection helps in understanding the role of the two parameters $\tau_i, \nu_i$ in PDMM. Interestingly, the step sizes $\tau_i$ and $\nu_i$ can be improved by considering the block sparsity of  $\bA$ and the number of random blocks $K$ to be updated.

\textbf{Sparsity of $\bA$:}  Assume $\bA$ is divided into $I\times J$ blocks. While $\x_j$ can be updated in parallel, the matrix multiplication $\bA\x$ in the dual update~\myref{eq:rpdmm0_y} requires synchronization to gather messages from all block coordinates $j_t\in\I_t$. For updating the $i$-th block of the dual $\y_i$, we need $\bA_i\x^{t+1}= \sum_{j_t \in \I_t}  \bA_{ij_t}\x_{j_t}^{t+1} + \sum_{k \notin \I_t}  \bA_{ik}\x_{k}^{t} $ which aggregates ``messages'' from all $\x_{j_t}$. If $\bA_{ij_t}$ is a block of zeros, there is no ``message'' from $\x_{j_t}$ to $\y_i$. More precisely, $\bA_i\x^{t+1}= \sum_{j_t \in \I_t \cap \cN(i) }  \bA_{ij_t}\x_{j_t}^{t+1} + \sum_{k \notin \I_t}  \bA_{ik}\x_{k}^{t} $ where $\cN(i)$ denotes a set of nonzero blocks in the $i$-th row block $\bA_i$. $\cN(i)$ can be considered as the set of neighbors of the $i$-th dual block $\y_i$ and $d_i = | \cN(i)|$ is the degree of the $i$-th dual block $\y_i$.
If $\bA$ is sparse, $d_i$ could be far smaller than $J$. According to Table~\ref{tbl:rpdmm_para}, a low $d_i$ will lead to bigger step sizes $\tau_i$ for the dual update and smaller step sizes for the dual backward step~\myref{eq:rpdmm_yhat}. Further, as shown in Section~\ref{sec:robcd}, when using PDMM with all blocks to solve composite minimization with overlapping blocks, PDMM can use $\tau_i = 0.5$ which is much larger than $1/J$ in sADMM.

\textbf{Randomized Blocks:}  The number of blocks to be randomly chosen also has the effect on $\tau_i, \nu_i$. If randomly choosing one block ($K = 1$), then $\nu_i = 0, \tau_i = \frac{1}{2J-1}$. The dual backward step~\myref{eq:rpdmm_yhat} vanishes. As $K$ increases, $\nu_i$ increases from $0$ to $1-\frac{1}{d_i}$ and $\tau_i$ increases from $\frac{1}{2J-1}$ to $\frac{1}{d_i}$. If updating all blocks ($K = J$), $\tau_i = \frac{1}{d_i}, \nu_i = 1-\frac{1}{d_i}$.

PDMM does not necessarily choose any $K$ combination of $J$ blocks. The $J$ blocks can be randomly partitioned into $J/K$ groups where each group has $K$ blocks. Then PDMM randomly picks one group.  A simple way is to permutate the $J$ blocks and choose $K$ blocks cyclically.

\subsection{Inexact PDMM}\label{sec:ipdmm}
If $\eta_{j_t} > 0 $, there is an extra Bregman divergence term in~\myref{eq:rpdmm_xi}, which can serve two purposes. First, choosing a suitable Bregman divergence can lead to a closed-form solution for~\myref{eq:rpdmm_xi}. Second, if $\eta_{j_t}$ is sufficiently large, the dual update can use a large step size ($\tau_i = 1$) and the backward step~\myref{eq:rpdmm_yhat} can be removed ($\nu_i = 0$), leading to the same updates as PJADMM~\cite{deng14:pmadmm} (see Section~\ref{sec:connect}).

Given a differentiable function $\psi_{j_t}$, its Bregman divergence is defiend as
\begin{align}
\!\!\!\!\!\!B_{\psi_{j_t}}(\x_{j_t},\x_{j_t}^t) \!=\! \psi_{j_t}(\x_{j_t}) \!-\! \psi_{j_t}(\x_{j_t}^t) \!-\! \langle \nabla \psi_{j_t}(\x_{j_t}^t), \x_{j_t} \!-\! \x_{j_t}^t\rangle,
\end{align}
where $\nabla \psi_{j_t}$ denotes the gradient of $\psi_{j_t}$. Rearranging the terms yields
\begin{align}
\!\!\!\!\!\!\psi_{j_t}(\x_{j_t}) \!-\! B_{\psi_{j_t}}(\x_{j_t},\x_{j_t}^t) \!=\!  \psi_{j_t}(\x_{j_t}^t) \!+\! \langle \nabla \psi_{j_t}(\x_{j_t}^t), \x_{j_t} \!-\! \x_{j_t}^t\rangle,
\end{align}
which is exactly the linearization of $\psi_{j_t}(\x_{j_t})$ at $\x_{j_t}^t$.  Therefore, if solving~\myref{eq:rpdmm_xi} exactly becomes difficult due to
some problematic terms, we can use the Bregman divergence to linearize these problematic terms so that~\myref{eq:rpdmm_xi} can be solved efficiently.
More specifically, in~\myref{eq:rpdmm_xi}, we can choose $\phi_{j_t} = \varphi_{j_t} -  \frac{1}{\eta_{j_t}}\psi_{j_t}$ assuming $\psi_{j_t}$ is the problematic term. Using the linearity of Bregman divergence,
\begin{align}\label{eq:bregman}
B_{\phi_{j_t}}(\x_{j_t},\x_{j_t}^t) =  B_{\varphi_{j_t}}(\x_{j_t},\x_{j_t}^t)- \frac{1}{\eta_{j_t}}B_{\psi_{j_t}}(\x_{j_t},\x_{j_t}^t)~.
\end{align}
For instance, if $f_{j_t}$ is a logistic function, solving~\myref{eq:rpdmm_xi} exactly requires an iterative algorithm.  Setting $\psi_{j_t} = f_{j_t}$, $\varphi_{j_t} = \frac{1}{2} \| \cdotp \|_2^2$ in~\myref{eq:bregman} and plugging into~\myref{eq:rpdmm_xi} yield
\begin{align}
& \x_{j_t}^{t+1} = \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ \langle \nabla f_{j_t}(\x_{j_t}^t), \x_{j_t}  \rangle + \langle \hat{\y}^{t}, \bA_{j_t}\x_{j_t} \rangle \nonumber \\
& + \frac{\rho}{2} \| \bA_{j_t}\x_{j_t} + \sum_{k \neq j} \bA_k\x_k^t - \a \|_2^2 + \eta_{j_t} \| \x_{j_t} - \x_{j_t}^{t} \|_2^2~,
\end{align}
which has a closed-form solution.
Similarly, if the quadratic penalty term $\frac{\rho}{2}\| \bA_{j_t}^c\x_{j_t} + \sum_{k \neq j}\bA_k^c\x_{j_t} - \a  \|_2^2$ is a problematic term, we can set $\psi_{j_t}(\x_{j_t}) = \frac{\rho}{2} \| \bA_{j_t}^c \x_{j_t} \|_2^2$, then $B_{\psi_{j_t}}(\x_{j_t},\x_{j_t}^t)  = \frac{\rho}{2} \| \bA_{j_t}^c(\x_{j_t} - \x_{j_t}^t) \|_2^2$ can be used to linearize the quadratic penalty term.

In~\myref{eq:bregman}, the nonnegativeness of $B_{\phi_{j_t}}$ implies that $B_{\varphi_{j_t}} \geq \frac{1}{\eta_{j_t}} B_{\psi_{j_t}}$.
This condition can be satisfied as long as $\varphi_{j_t}$ is more convex than $\psi_{j_t}$. Technically, we assume that $\varphi_{j_t}$ is $\sigma/\eta_{j_t}$-strongly convex and $\psi_{j_t}$ has Lipschitz continuous gradient with constant $\sigma$, which has been shown in~\cite{wang13:badmm}. For instance, if $\psi_{j_t}(\x_{j_t}) = \frac{\rho}{2} \| \bA_{j_t}^c \x_{j_t} \|_2^2$, $\sigma = \rho \lambda_{\max}(\bA_{j_t}^c)$ where $\lambda_{\max}(\bA_{j_t}^c)$ denotes the largest eigenvalue of $(\bA_{j_t}^c)^T\bA_{j_t}^c$. If choosing $\varphi_{j_t} = \frac{1}{2}\| \cdotp \|_2^2$, the condition is satisfied by setting $\eta_{j_t} \geq \rho \lambda_{\max}(\bA_{j_t}^c)$.

\iffalse
\subsection{PDMM without Dual Step}
In PDMM, the dual step can be eliminated by setting $\tau_i = 0$ and $\y^t = \y^0$. The dual backward step simply shrinks the residual $\bA\x - \a$. By substituting into the $\x_j$ update, PDMM reduces to an extremely simple algorithm:
\begin{align}\label{eq:pdmmnodual}
\x_{j_t}^{t+1}  = \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~f_{j_t}(\x_{j_t}) + \sum_{i=1}^{I} (1-\nu_i) \rho\langle \bA_i^r\x^t - \a_i, \bA_{ij_t}\x_{j_t}\rangle + \frac{\rho}{2} \| \bA_{j_t}^c(\x_{j_t} - \x_{j_t}^t) \|_2^2 + \eta_{j_t} B_{\phi_{j_t}}(\x_{j_t}, \x_{j_t}^{t})~,
\end{align}
where $\nu_i = 1-\frac{2J}{\tilde{K_i}(2J-K)} $. If $d_i \geq 2$ and $K \leq 2$, $\tilde{K}_i \geq 2$ and thus $\nu_i \geq 0$.
PDMM can run in parallel and asynchronously. The algorithm is summarized in Algorithm~\ref{algo:pdmmnodual}. The convergence is given in Appendix~\ref{app:pdmmnodual}.

\begin{algorithm*}[!tb]
\caption{Parallel Diretion Method of Multipliers without Dual Step}
\label{algo:pdmmnodual}
\begin{algorithmic}[1]
\STATE {\bfseries Input: $\rho, \eta_j, \tau_i, \nu_i$}
\STATE {\bfseries Initialization:} $\x^1$
\STATE if $\tau_i, \nu_i$ are not defined, initialize $\tau_i, \nu_i$ as given in Table~\ref{tbl:rpdmm_para}
\STATE $\r^1 = \bA\x^1 - \a = -\a$
\FOR{$t=1 \text{ to } T$}
\STATE randomly pick up $j_t$ block coordinates
\STATE $ \x_{j_t}^{t+1} = \underset{\x_{j_t}\in\cX_{j_t}}{\argmin}~ f_{j_t}(\x_{j_t}) + \sum_{i=1}^{I} (1-\nu_i)\rho\langle \r_i^t , \bA_{ij_t}\x_{j_t} \rangle + \frac{\rho}{2} \| \bA_{j_t}^c(\x_{j_t} - \x_{j_t}^t) \|_2^2 + \eta_{j_t} B_{\phi_{j_t}}(\x_{j_t}, \x_{j_t}^{t})$
\STATE $\r^{t+1} = \r^t + \sum_{j_t \in \mathbb{I}_t } \bA_{j_t}^c(\x_{j_t}^{t+1} - \x_{j_t}^t)$
\ENDFOR
\end{algorithmic}
\end{algorithm*}
\fi

\subsection{Connections to Related Work}\label{sec:connect}

\textbf{All blocks:} There are also two other methods which update all blocks in parallel.
If solving the primal updates exactly, two-block ADMM with splitting variables (sADMM) is considered in ~\cite{pari14:prox,luo13:padmm}.
We show that sADMM is a special case of PDMM when setting $\tau_i = \frac{1}{J}$ and $\nu_i = 1 -\frac{1}{J}$ ( See Appendix~\ref{app:sadmm}).
If the primal updates are solved inexactly, ~\cite{deng14:pmadmm} considers a proximal Jacobian ADMM (PJADMM) by adding proximal terms where the converge rate is improved to $o(1/T)$ given the sufficiently large proximal terms. We show that PJADMM~\cite{deng14:pmadmm} is also a special case of PDMM ( See Appendix~\ref{app:pjadmm}).  sADMM and PJADMM are two extreme cases of PDMM.
The connection between sADMM and PJADMM through PDMM can provide better understanding of the three methods and the role of dual backward step. If the primal update is solved exactly which makes sufficient progress, the dual update should take small step, e.g., sADMM. On the other hand, if the primal update takes small progress by adding proximal terms, the dual update can take full gradient step, e.g. PJADMM. While sADMM is a direct derivation of ADMM, PJADMM introduces more terms and parameters.

\textbf{Randomized blocks:} While PDMM can randomly update any number of blocks, RBUSMM~\cite{hong13:bcdmm} can only randomly update one block.  The convergence of RBSUMM requires certain local error bounds to be hold and decreasing step size. Moreover, the iteration complexity of RBSUMM is still unknown. In contast, PDMM converges at a rate of $O(1/T)$ with the constant step size.

\subsection{Randomized Overlapping Block Coordinate}\label{sec:robcd}
Consider the composite minimization problem of a sum of a loss function $\ell(\w)$ and composite regularizers $g_j(\w_j)$:
\begin{align}\label{eq:overlap}
\min_{\w}~ \ell(\w) + \sum_{j=1}^L g_j( \w_j )~,
\end{align}
which considers $L$ overlapping groups $\w_j\in\R^{b\times 1}$. Let $J = L+1, \x_{J} = \w$.
For $1\leq j \leq L$, denote $\x_j = \w_j$, then $\x_j = \bU_j^T \x_{J}$, where $\bU_j \in \R^{b\times L}$ is the columns of an identity matrix and extracts the coordinates of $\x_{J}$. Denote $\bU = [\bU_1, \cdots,\bU_L]\in \R^{n\times (bL)}$ and $\bA = [\bI_{bL},-\bU^T]$ where $bL$ denotes $b\times L$. By letting $f_j(\x_j) =g_j(\w_j)$ and $f_{J}(\x_{J}) = \ell(\w)$,
~\myref{eq:overlap} can be written as:
\begin{align}\label{eq:pdmm_overlap}
\min_{\x}~ \sum_{j=1}^{J} f_j(\x_j) ~\quad\text{s.t.}\quad \bA\x = \mathbf{0}.
\end{align}
where $\x = [\x_1;\cdots;\x_L;\x_{L+1}] \in \R^{b\times J}$. ~\myref{eq:pdmm_overlap} can be solved by PDMM in a randomized block coordinate fashion.  In $\bA$, for $b$ rows block, there are only two nonzero blocks, i.e., $d_i = 2$. Therefore, $\tau_i = \frac{K}{2(2J-K)}, \nu_i = 0.5$. In particular, if $K = J$, $ \tau_i = \nu_i = 0.5$. In contrast, sADMM uses $\tau_i = 1/J \ll 0.5, \nu_i = 1 - 1/J > 0.5$ if $J$ is larger.

\begin{remark}
(a) ADMM~\cite{boyd10} can solve~\myref{eq:pdmm_overlap} where the equality constraint is $\x_j = \bU_j^T \x_{J}$.

(b) In this setting, Gauss-Seidel ADMM (GSADMM) and BSUMM~\cite{hong13:bcdmm} are the same as ADMM. BSUMM should converge with constant stepsize $\rho$ (not necessarily sufficiently small), although the theory of BSUMM does not include this special case.

(c) Consensus optimization~\cite{boyd10} has the same formulation as~\myref{eq:pdmm_overlap}. Therefore, PDMM can also be used as a randomized consensus optimization algorithm.
\end{remark}