Abstract: Box set subtraction is widely used in SAMR to compute data dependency and nested restriction. Traditional box set subtraction algorithms suffer from high time complexity, which often dominates execution time for large scale SAMR simulations. In this paper, a divide and conquer box set subtraction algorithm with linear time complexity was proposed, and enhanced by domain decomposition parallelization. Experiment results on regular box set and irregular box set of SAMR application verify linear time complexity property. And for large scale problems, our algorithm shows great improvement on computing time.