Boolean matrices are a special case of matrices whose entries are bounded integers (Bounded Integer Matrices). Multiplication of nxn Bounded Integer Matrices with 0(n ?log2 loglog n logloglog n) bit operations is made possible by the use of a new class of algorithms approximating the result with an arbitrarily small error. The value log121000=27299 has been found for ?. A significant improvement of the upper bound to complexity of Boolean matrix multiplication is thus obtained.
A new class of boolean matrix multiplication algorithms
1978
Abstract
Boolean matrices are a special case of matrices whose entries are bounded integers (Bounded Integer Matrices). Multiplication of nxn Bounded Integer Matrices with 0(n ?log2 loglog n logloglog n) bit operations is made possible by the use of a new class of algorithms approximating the result with an arbitrarily small error. The value log121000=27299 has been found for ?. A significant improvement of the upper bound to complexity of Boolean matrix multiplication is thus obtained.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_422119-doc_150028.pdf
solo utenti autorizzati
Descrizione: A new class of boolean matrix multiplication algorithms
Dimensione
451.7 kB
Formato
Adobe PDF
|
451.7 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
