Several data mining applications such as recommender systems and online advertising involve the analysis of large, heterogeneous dyadic data, where the data consists of measurements on pairs of elements, each from a different set of entities. Independent variables (covariates) are additionally associated with the entities along the two modes and their combination. This paper focuses on developing a general, "divide and conquer" approach for predictive modeling of large-scale dyadic data that decomposes the problem in a flexible manner into multiple local sub-problems. Apart from improving prediction accuracy over alternative approaches, our approach allows for massive parallelization, which is essential to handle the scale of data processed by business applications today. Our work is distinguished from prior approaches that either use a global modeling technique as well as partitional approaches that impose rigid structural constraints and hence offer limited opportunities for parallelization.