Let $n>k$, $n|q-1$. We have an $k*k$ linear system of equations $Ax=b$ over a finite field $\mathbb{F}_q$. Matrix $A$ is full rank and it is a submatrix of Vandermonde matrix $V$ corresponding to $n$th root of unity $w\in \mathbb{F}_q$. The rows of $A$ are the first $k$ rows of $V$ and its column indices are in set $S$ where $S\subset \{1,\ldots,n\}$ and $|S|=k$. For example if $q=11$, $n=10$, $k=5$, $S=\{1,3,4,6,8\}$ and $w$ be $10$th root of unity, then row $1$ is $(1,\ldots,1)$, row $2$ is $(w^1,w^3,w^4,w^6,w^8)$ and then continue the vandermonde structure for other rows.
How can we solve this linear system in an efficient way? By efficient I mean something like fast Fourier transform (FFT) algorithm. We consider $n,k$ to be big enough.
note: If A is a vandermonde matrix corresponding to $k$th roots of unity, then the inverse of $A$ is still Vandermonde matrix and system can be solved with an inverse FFT algorithm. In our case the inverse of $A$ is not a Vandermonde matrix.
The same problem can be translated to the following:
We have a polynomial $z(x)=\sum\limits_{i=0}^{n-1} z_ix^i$ of degree $<n$ which has $k$ known nonzero distinct roots, i.e, $gcd(x^n-1,z(x))$ is known. Coefficients $z_k,\ldots, z_{n-1}$ are known while $z_0,\ldots,z_{k-1}$ are unknown. How we can compute $z_o,\ldots, z_{k-1}$ efficiently? Back to our example above, $\{w^1,w^3,w^4,w^6,w^8\}$ are roots of $gcd(x^n-1,z(x))$ which has degree $|S|$. As an extra side information, we know the rank of the circulant matrix associated with polynomial $z(x)$.