The theory of belief functions is a very appealing theory for uncertainty modeling and reasoning which has been widely used in information fusion. However, when the cardinality of the frame of discernment and the number of the focal elements are large the fusion of belief functions requires in general a high computational complexity.