A fast procedure for the exact computation of the performance of complex probabilistic systems

A new set-theoretic method for the exact and efficient computation of the probabilistic performance of complex systems has been developed. The core of the method is a fast algorithm for disjointing a collection of sets which is intended for systems with more than 1,000 components and 100,000 cut sets. The method is based on a ''divide and conquer'' approach where a multidimensional problem is progressively decomposed into sub-problems along its dimensions. The method also uses a particular pointer system which eliminates the need to store the subproblems, but only requires to store pointers to those problems. Examples of the algorithm and the divide and conquer strategy are provided, and comparisons with other significant methods are made. Statistical and worst case complexity studies show that the time and space complexity of other typical methods is O(me/sup n/), but that our method is O(m2n2). Large-scale systems which can only be approximated with other methods can now be evaluated exactly