Oracle computations in parallel numerical linear algebra (Q1325837)

Using a new notion of reducibility, the authors investigate the behaviour of several known reductions among important problems in linear algebra. The main concern is the relative parallel-time complexity of certain problems within the class NC. It is shown that, within the computational model considered, many known reduction algorithms do not extend whereas the extension of other ones requires additional care.