Is there a fast algorithm to check for AR(p) stationarity? It is well-known that an AR(p) process 
$$
x_t=\sum_{i=1}^p \varrho_i x_{t-i} + \epsilon_t \,,
$$
is causal and stationary if and only if the roots of the polynomial
$$
\mathcal{P}(u) = 1 - \sum_{i=1}^p \varrho_i u^i
$$
are all outside the unit circle in the complex plane. (Here is a Cross Validated discussion on the topic.)
My question is whether or not there exists a faster algorithm than the naïve one that consists in (a) finding the roots of $\mathcal{P}$ and (b) checking none one them is inside the unit circle.
 A: The Schur-Cohn algorithm has $d=2$; this is what I learned in a computational statistics class at Berkeley some years ago.
A: It is unnecessary to find the $p$ complex roots as far as
these are not to be used for themselves. Moreover, most (if not all)
root finding processes can fail for large $p$.
Another solution is as follows.
The $\mathrm{AR}(p)$ model can be reparametrised thanks to its $p$
partial autocorrelations (PACs) $\zeta_k$ for $1 \le k \le p$.  The PACs are often denoted as $\phi_{k,k}$ because their
computation involves an array $\phi_{k,\ell}$. There is a one-to-one
correspondence between the vector $\boldsymbol{\rho}$ of the $p$
coefficients in the stationarity region and the vector
$\boldsymbol{\zeta}$ in the region defined by the $p$ conditions
$|\zeta_k | < 1$ for $1 \le k \le p$.  The transformation "AR to
PAC" $\boldsymbol{\rho} \mapsto \boldsymbol{\zeta}$ is quite simple
and is given as a pretty recursion formula due to Barndorff-Nielsen
and Schou. Testing stationarity from the vector of coefficients boils
down to computing the $\zeta_k$ and stop as soon as one condition $|
\zeta_k | \ge 1$ is found.
The less well-known inverse transform "PAC to AR"
$\boldsymbol{\zeta} \mapsto \boldsymbol{\rho}$ is available explicitly
(due to Monahan), and is as simple as is the direct one. It might also
be useful in some cases.
The two transformations are implemented (in R) in a CRAN R package named
FitAR which provides as well an efficient
invertibleQ function to test stationarity. The package is
described in the following article where list of references is
provided.
McLeod, A.I. and Zhang Y., "Improved Subset Autoregression: With R Package"
Journal of Statistical Software, vol. 28, Issue 2, Oct 2008.
http://www.jstatsoft.org/v28/i02
