Bulk-synchronous parallel Gaussian elimination (Q5959711)

Two algorithms for bulk synchronous parallel Gaussian elimination are presented: one without pivoting and the other with a local pivoting scheme. Computational and theoretical arguments are utilized to show that both the algorithms are more efficient in terms of communications but not in synchronization. This fact is used to trade off, in a certain range, the costs of communication and synchronization to achieve optimal or near-optimal cost values at the extremes of this range. It is pointed out that for large problems, a communication-efficient algorithm may be preferable to a synchronization-efficient one.