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 / B., Codenotti; Leoncini, Mauro; G., Resta. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 127:(1994), pp. 99-121.
Oracle Computations in Parallel Numerical Linear Algebra
LEONCINI, Mauro;
1994
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 modelPubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris