  This paper focuses on finite-time in-network computation of linear transforms
of distributed graph data. Finite-time transform computation problems are of
interest in graph-based computing and signal processing applications in which
the objective is to compute, by means of distributed iterative methods, various
(linear) transforms of the data distributed at the agents or nodes of the
graph. While finite-time computation of consensus-type or more generally
rank-one transforms have been studied, systematic approaches toward scalable
computing of general linear transforms, specifically in the case of
heterogeneous agent objectives in which each agent is interested in obtaining a
different linear combination of the network data, are relatively less explored.
In this paper, by employing ideas from algebraic geometry, we develop a
systematic characterization of linear transforms that are amenable to
distributed in-network computation in finite-time using linear iterations.
Further, we consider the general case of directed inter-agent communication
graphs. Specifically, it is shown that \emph{almost all} linear transformations
of data distributed on the nodes of a digraph containing a Hamiltonian cycle
may be computed using at most $N$ linear distributed iterations. Finally, by
studying an associated matrix factorization based reformulation of the
transform computation problem, we obtain, as a by-product, certain results and
characterizations on sparsity-constrained matrix factorization that are of
independent interest.
