TY - GEN
T1 - 3D rectangulations and geometric matrix multiplication
AU - Floderus, Peter
AU - Jansson, Jesper Andreas
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
AU - Sledneu, Dzmitry
PY - 2014/1/1
Y1 - 2014/1/1
N2 - The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case in which P is a 3D histogram. It runs in O(mlogm) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n×n matrices A and B with nonnegative integer entries, yielding a method for computing A × B in Õ(n2+min{rArB, n min{rA, rB}}) time, where Õ suppresses polylogarithmic (in n) factors and where rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
AB - The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case in which P is a 3D histogram. It runs in O(mlogm) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n×n matrices A and B with nonnegative integer entries, yielding a method for computing A × B in Õ(n2+min{rArB, n min{rA, rB}}) time, where Õ suppresses polylogarithmic (in n) factors and where rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
KW - Geometric decompositions
KW - Matrix multiplication
KW - Minimum number rectangulation
KW - Polyhedron
KW - Time complexity
UR - http://www.scopus.com/inward/record.url?scp=84921641440&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13075-0_6
DO - 10.1007/978-3-319-13075-0_6
M3 - Conference article published in proceeding or book
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 65
EP - 78
BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
A2 - Ahn, Hee-Kap
A2 - Shin, Chan-Su
T2 - 25th International Symposium on Algorithms and Computation, ISAAC 2014
Y2 - 15 December 2014 through 17 December 2014
ER -