𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On parallel block algorithms for exact triangularizations

✍ Scribed by Jean-Guillaume Dumas; Jean-Louis Roch

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
443 KB
Volume
28
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

We present a new parallel algorithm to compute an exact triangularization of large square or rectangular and dense or sparse matrices in any field. Using fast matrix multiplication, our algorithm has the best known sequential arithmetic complexity. Furthermore, on distributed architectures, it drastically reduces the total volume of communication compared to previously known algorithms. The resulting matrix can be used to compute the rank or to solve a linear system. Over finite fields, for instance, our method has proven useful in the computation of large Gr€ o obner bases arising in robotic problems or wavelet image compression.

πŸ“œ SIMILAR VOLUMES

Exact algorithms for scheduling multiple
Exact algorithms for scheduling multiple families of jobs on parallel machines
✍ Zhi-Long Chen; Warren B. Powell πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

## Abstract In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent o