Polynomial collocation method I was reading this article (https://pdfs.semanticscholar.org/6b11/ff0dcf14991f7be50e354d85c932409a01d9.pdf) on colloaction method, where author has considered the IVP $$y'(t)=f(t,y(t))~~,~~t \in I=[0,T]~~,~~y(0)=y_0$$ Assume $f:I \times \Omega \subset \mathbb{R} \to \mathbb{R}$ is Lipschitz. Now define a mesh $I_h=\{t_n : 0=t_0 <t_1< \ldots <t_N=T\}$ and $h_n=t_{n+1}-t_n$ and $h=\text{max} \{h_n: 0 \le n \le N-1 \}$ which is the step size. Now the solution will be approximated by an element $u_h$ of the polynomial space
$$S^{(0)}_m(I_h)=\{v \in C(I): v|_{[t_n,t_{n+1}]} \in \pi_m\}$$ Where $\pi_m$denotes the space of all real polynomials of degree less than or equal to $m$. Then author has written  that $dim\,S^{(0)}_m(I_h)\,=Nm+1$ , which im having a little difficulty to understand.Another doubt is does $u_h$ is getting approximated as a polynomial in every single intervals in the mesh or over the whole range ?
Also the author has defined a set of collocation points $X_h=\{t=t_n+c_ih_n:0 \le c_1 \le \ldots <c_m \le 1\}$ and its cardinality as 
$$\begin{align}|X_h|&=Nm ~\text{if}~0 < c_1 < \ldots <c_m \le 1 ,\\&=N(m-1)+1 ~\text{if}~0 < c_1 < \ldots <c_m = 1 ,m \ge 2 \tag{*}\end{align}$$I'm also having difficulty to understand $(*)$.
Also in general what is the difference between RK methods and Collocation , what extra advantage collocation provide over RK methods ? 
 A: I start from the end: collocation methods are a subclass of implicit Runge-Kutta methods, which can be found even from the Wikipedia page of collocation methods.
Gauss-Legendre Runge-Kutta methods, for example, are collocation methods based on Gauss-Legendre quadrature points. Their advantages are multiple. For example, they have high order ($2s$ for a method on $s$ stages), and they have great properties in geometric problems (conservation of quadratic invariants, symplecticity...). Another class of collocation methods are the Radau methods, which are $A$ and $L$-stable, making them an extremely good candidate for integrating stiff equations (order $2s-1$ for $s$ stages).
Regarding the dimension of $S_m^{(0)}(I_h)$, you have $N$ intervals, and on each interval a polynomial of degree $m$. In total, therefore, you have $N\cdot (m+1)$ degrees of freedom, which give the dimension of the space. Or does it? You have to impose continuity at the internal extrema of the intervals, therefore you have $N-1$ constraints (free ends): therefore
$$
\dim{S_m^{(0)}(I_h)} = Nm + N - N + 1 = Nm+1.
$$
The only doubt I have about this, is that if you impose the initial condition you get an additional constraint, which would make the dimension just $Nm$. A similar reasoning yields the cardinality of the set $X_h$.
An excellent treatment of collocation methods, which is very accessible too, can be found in Solving Ordinary Differential Equations I, by Hairer, Norset, Wanner (within Chapter 2.7 in the second edition). The equivalence with RK methods is shown in details. In the other books by the same authors (without Norsett and/or with Lubich) Solving ODEs II and Geometric Numerical Integration collocation methods are more or less treated and appear ubiquitously.
