{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:28Z","timestamp":1787340868316,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:p>Brent\u2019s scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm. Such a scheme preserves, under slow-down, the actual number of executed operations, also called work. In this paper we take the complementary viewpoint, and rather than consider the work-preserving slow-down of some fast parallel algorithm, we investigate the problem of the achievable speedups of computation while preserving the work of the best-known sequential algorithm for the same problem. The proposed technique, eminently applicable to problems of matrix-computational flavor, achieves its result through the interplay of two algorithms with significantly different features. Analogous but structurally different \u201cinterplays\u201d have been used previously to improve the algorithmic efficiency of graph computations, selection, and list ranking. We demonstrate the efficacy of our technique for the computation of path aigebras in graphs and digraphs and various fundamental computations in linear algebra. Some of the fundamental new algorithms may have practical value; for instance, we substantially improve the algorithmic performance of the parallel solution of triangular and Toeplitz linear systems of equations and the computation of the transitive closure of digraphs.<\/jats:p>","DOI":"10.1137\/0224051","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:42:53Z","timestamp":1109227373000},"page":"811-821","source":"Crossref","is-referenced-by-count":6,"title":["Work-Preserving Speed-Up of Parallel Matrix Computations"],"prefix":"10.1137","volume":"24","author":[{"given":"Victor Y.","family":"Pan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90161-5"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R5","volume-title":"The computational complexity of algebraic and numeric problems","author":"Borodin Allan","year":"1975"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Bini, V. Y. Pan,  Parallel polynomial computations by recursive processes,  Proc. ACM SIGSAM Intern. Symp. on Symb. and Alg. Comp. (ISSAC-90), ACM Press, NY,  1990,  294\u2013","DOI":"10.1145\/96877.96963"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0222041"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3"},{"key":"R9","volume-title":"Graphs and networks","author":"Carr\u00e9 Bernard","year":"1979"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028792"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0908073"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"R15","volume-title":"Matrix computations","author":"Golub Gene H.","year":"1989"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90173-7"},{"key":"R17","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e0J\u00e0 J.","year":"1992"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(79)90124-0"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, V. Y. Pan,  Processor efficient parallel solution of linear systems over an abstract field,  Proc. 3rd Annual ACM Symp. on Parallel Algorithms and Architecture, Hilton Head, SC, ACM Press, New York,  1991,  180\u2013191","DOI":"10.1145\/113379.113396"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, V. Y. Pan,  Parallel and processor efficient solution of linear systems II: The general case,  Proc. 33rd IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, IEEE Computer Society Press, Los Alamitos, CA,  1992,  714\u2013723 0977.68879","DOI":"10.1109\/SFCS.1992.267779"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90393-O"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Morf,  Doubling algorithms for Toeplitz and related equations,  Proc. IEEE Intern. Conference on ASSP, IEEE Computer Society Press,  1980,  954\u2013959","DOI":"10.1109\/ICASSP.1980.1171074"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90019-3"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023051-7"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-76717-3_2"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(92)90215-4"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/1034049"},{"key":"R29","first-page":"621","volume-title":"Synthesis of Parallel Algorithms","author":"Pan V. Y.","year":"1993"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0614010"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"V. Y. Pan, F. P. Preparata,  Supereffective slow-down of parallel computations,  Proc. 4th Annual ACM Symp. on Parallel Algorithms and Architectures, San Diego, CA, ACM Press, New York,  1992,  402\u2013409","DOI":"10.1145\/140901.141926"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90013-5"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90079-0"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90006-X"},{"key":"R35","unstructured":"T. Spencer,  Time-work tradeoffs for parallel graph algorithms,  Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1991), ACM, New York,  1991,  425\u2013432 1 095 8590800.68645"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"T. Spencer,  More time-work tradeoffss for parallel graph algorithms,  Proc. 3rd Annual ACM Symp. on Parallel Algorithms and Architectures, Hilton Head, SC, ACM Press, New York,  1991,  81\u201393","DOI":"10.1145\/113379.113387"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90010-9"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0224051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:53:35Z","timestamp":1787338415000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0224051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1137\/0224051"],"URL":"https:\/\/doi.org\/10.1137\/0224051","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}