  It is well known that, whenever $k$ divides $n$, the complete $k$-uniform
hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings.
Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into
parallel classes so that each parallel class is a partition of the $n$-set.
This result is known as Baranyai's theorem, which guarantees the existence of
\emph{Baranyai partitions}. Unfortunately, the proof of Baranyai's theorem uses
network flow arguments, making this result non-explicit. In particular, there
is no known method to produce Baranyai partitions in time and space that scale
linearly with the number of hyperedges in the hypergraph. It is desirable for
certain applications to have an explicit construction that generates Baranyai
partitions in linear time. Such an efficient construction is known for $k=2$
and $k=3$. In this paper, we present an explicit recursive quadrupling
construction for $k=4$ and $n=4t$, where $t \equiv 0,3,4,6,8,9
~(\text{mod}~12)$. In a follow-up paper (Part II), the other values of~$t$,
namely $t \equiv 1,2,5,7,10,11 ~(\text{mod}~12)$, will be considered.
