The time-recursive computation has been proved as a particularly useful tool in real-time data compression, in transform domain adaptive filtering and in spectrum analysis. Unlike the FFT based ones, the time-recursive architectures require only local communication. Also, they are modular and regular, thus they are very appropriate for VLSI implementation and they allow high degree of parallelism. In this two part paper, we establish an architectural frame work for parallel time-recursive computation. In part I, we consider a class of linear operators that consists of the discrete time, time invariant, compactly supported, but otherwise arbitrary kernel functions. We show that the structure of the realization of a given linear operator is dictated by the decomposition of the latter with respect to proper basis functions. An optimal way for carrying out this decomposition is demonstrated. The parametric forms of the basis functions are identified and their properties pertinent to the architecture design are studied. A library of architectural building modules capable of realizing these functions is developed. An analysis of the implementation complexity for the aforementioned modules is conducted. Based on this framework, an architecture design procedure is developed in Part II [12] that can be used for routinely obtaining the time-recursive architecture of a given linear operator.