Using a new notion of reducibility, we investigate, in a model of approximate parallel computation, the behaviour of several known reductions among important problems in linear algebra. We show that, although many such problems have been proved to be NC1 equivalent, when approximation is taken into account, new questions about their relative parallel-time complexity come up. More precisely, some known NC1 reduction algorithms can be extended with additional special care, whereas other reductions do not extend to the approximation model
Oracle Computations in Parallel Numerical Linear Algebra
LEONCINI, MAURO;
1994-01-01
Abstract
Using a new notion of reducibility, we investigate, in a model of approximate parallel computation, the behaviour of several known reductions among important problems in linear algebra. We show that, although many such problems have been proved to be NC1 equivalent, when approximation is taken into account, new questions about their relative parallel-time complexity come up. More precisely, some known NC1 reduction algorithms can be extended with additional special care, whereas other reductions do not extend to the approximation modelFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
