Sequential optimization of matrix chain multiplication relative to different cost functions

Igor Chikalov; Shahid Hussain; Mikhail Moshkov

doi:10.1007/978-3-642-18381-2_13

Sequential optimization of matrix chain multiplication relative to different cost functions

Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Scopus citations

Abstract

In this paper, we present a methodology to optimize matrix chain multiplication sequentially relative to different cost functions such as total number of scalar multiplications, communication overhead in a multiprocessor environment, etc. For n matrices our optimization procedure requires O(n 3) arithmetic operations per one cost function. This work is done in the framework of a dynamic programming extension that allows sequential optimization relative to different criteria. © 2011 Springer-Verlag Berlin Heidelberg.

Original language	English (US)
Title of host publication	SOFSEM 2011: Theory and Practice of Computer Science
Publisher	Springer Nature
Pages	157-165
Number of pages	9
ISBN (Print)	9783642183805
DOIs	https://doi.org/10.1007/978-3-642-18381-2_13
State	Published - 2011

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-18381-2_13

Cite this

@inproceedings{0d1ea2b33a9d495995fb973473bd77cd,

title = "Sequential optimization of matrix chain multiplication relative to different cost functions",

abstract = "In this paper, we present a methodology to optimize matrix chain multiplication sequentially relative to different cost functions such as total number of scalar multiplications, communication overhead in a multiprocessor environment, etc. For n matrices our optimization procedure requires O(n 3) arithmetic operations per one cost function. This work is done in the framework of a dynamic programming extension that allows sequential optimization relative to different criteria. {\textcopyright} 2011 Springer-Verlag Berlin Heidelberg.",

author = "Igor Chikalov and Shahid Hussain and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2011",

doi = "10.1007/978-3-642-18381-2_13",

language = "English (US)",

isbn = "9783642183805",

pages = "157--165",

booktitle = "SOFSEM 2011: Theory and Practice of Computer Science",

publisher = "Springer Nature",

}

TY - GEN

T1 - Sequential optimization of matrix chain multiplication relative to different cost functions

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2011

Y1 - 2011

N2 - In this paper, we present a methodology to optimize matrix chain multiplication sequentially relative to different cost functions such as total number of scalar multiplications, communication overhead in a multiprocessor environment, etc. For n matrices our optimization procedure requires O(n 3) arithmetic operations per one cost function. This work is done in the framework of a dynamic programming extension that allows sequential optimization relative to different criteria. © 2011 Springer-Verlag Berlin Heidelberg.

AB - In this paper, we present a methodology to optimize matrix chain multiplication sequentially relative to different cost functions such as total number of scalar multiplications, communication overhead in a multiprocessor environment, etc. For n matrices our optimization procedure requires O(n 3) arithmetic operations per one cost function. This work is done in the framework of a dynamic programming extension that allows sequential optimization relative to different criteria. © 2011 Springer-Verlag Berlin Heidelberg.

UR - http://hdl.handle.net/10754/564333

UR - http://link.springer.com/10.1007/978-3-642-18381-2_13

UR - http://www.scopus.com/inward/record.url?scp=78751667811&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18381-2_13

DO - 10.1007/978-3-642-18381-2_13

M3 - Conference contribution

SN - 9783642183805

SP - 157

EP - 165

BT - SOFSEM 2011: Theory and Practice of Computer Science

PB - Springer Nature

ER -

Sequential optimization of matrix chain multiplication relative to different cost functions

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this