# US 8,543,626 B2 · Method and apparatus for QR-factorizing matrix on a multiprocessor system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,626 B2 - Document ID: US8543626B2 - Status: Granted - Kind: B2 - Application number: 13/559,885 - Filed: 2012-07-27 - Published: 2012-11-22 - Granted: 2013-09-24 - Earliest claimed: 2008-03-14 - Assignees: International Business Machines Corporation - Applicants: Hui Li; Bai Ling Wang - Inventors: Hui Li; Bai Ling Wang - Web page: https://patentgrep.com/patent/US8543626B2 ## CPC - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method and apparatus for QR-factorizing matrix on a multiprocessor system, wherein the multiprocessor system comprises at least one core processor and a plurality of accelerators, comprises the steps of: iteratively factorizing each panel in the matrix until the whole matrix is factorized; wherein in each iteration, the method comprises: partitioning an unprocessed matrix part in the matrix into a plurality of blocks according to a predetermined block size; partitioning a current processed panel in the unprocessed matrix part into at least two sub panels, wherein the current processed panel is composed of a plurality of blocks; and performing QR factorization one by one on the at least two sub panels with the plurality of accelerators, and updating the data of the sub panel(s) on which no QR factorization has been performed among the at least two sub panels by using the factorization result. ## Claims ### Claim 1 A method for QR-factorizing matrix on a multiprocessor system, wherein the multiprocessor system comprises at least one core processor and a plurality of accelerators, the method comprising the step of: iteratively factorizing each panel in the matrix until the whole matrix is factorized; wherein in each iteration, the method comprises: partitioning an unprocessed matrix part in the matrix into a plurality of blocks according to a predetermined block size; partitioning a current processed panel in the unprocessed matrix part into at least two sub panels, wherein the current processed panel is composed of a plurality of blocks; and performing QR factorization one by one on the at least two sub panels with the plurality of accelerators, and updating the data of the sub panel(s) on which no QR factorization has been performed among the at least two sub panels by using the factorization result. ### Claim 2 (depends on 1) The method according to claim 1, wherein the predetermined block size is 64×64. ### Claim 3 (depends on 1) The method according to claim 1, wherein the step of partitioning a current processed panel in the unprocessed matrix part into at least two sub panels further comprises the step of: partitioning the current processed panel in the unprocessed matrix part into a left sub panel and a right sub panel. ### Claim 4 (depends on 3) The method according to claim 3, wherein the sizes of the left sub panel and the right sub panel are unequal. ### Claim 5 (depends on 3) The method according to claim 3, wherein the sizes of the left sub panel and the right sub panel are equal. ### Claim 6 (depends on 3) The method according to claim 3, wherein the step of performing QR factorization one by one on the at least two sub panels with the plurality of accelerators and updating the data of the sub panel(s) on which no QR factorization has been performed among the at least two sub panels by using the factorization result further comprises the steps of: performing QR factorization operation on the left sub panel; computing the triangular factor of the left sub panel based on the result of the QR factorization operation; updating the data of the right sub panel by using the left sub panel and the triangular factor of the left sub panel; and performing QR factorization operation on updated right sub panel. ### Claim 7 (depends on 6) The method according to claim 6, further comprising in each iteration: computing the triangular factor of the current processed panel which is the whole of the at least two sub panels after QR factorization operation is performed on all the at least two sub panels; and updating the data of the matrix part on which no iteration operation has been performed in the unprocessed matrix part by using the current processed panel and its triangular factor. ### Claim 8 (depends on 1) The method according to claim 1, wherein the step of performing QR factorization one by one on the at least two sub panels with the plurality of accelerators and updating the data of the sub panel(s) on which no QR factorization has been performed among the at least two sub panels by using the factorization result further comprises the step of: distributing the matrix data required for the QR factorization operation from a main memory of the multiprocessor system to the plurality of accelerators in a row-column periodic block partitioning manner. ### Claim 9 An apparatus for QR-factorizing matrix on a multiprocessor system, wherein the multiprocessor system comprises at least one core processor and a plurality of accelerators, the apparatus factorizes each panel in the matrix iteratively until the whole matrix is factorized, the apparatus comprising: a block partitioning unit configured to, in each iteration, partition an unprocessed matrix part in the matrix into a plurality of blocks according to a predetermined block size; a panel partitioning unit configured to, in each iteration, partition a current processed panel in the unprocessed matrix part into at least two sub panels, wherein the current processed panel is composed of a plurality of blocks; and a sub panel processing unit configured to, in each iteration, perform QR factorization one by one on the at least two sub panels with the plurality of accelerators, and update the data of the sub panel(s) on which no QR factorization has been performed among the at least two sub panels by using the factorization result. ### Claim 10 (depends on 9) The apparatus according to claim 9, wherein the panel partitioning unit partitions the current processed panel into a left sub panel and a right panel; and the sub panel processing unit further comprises: a sub panel QR factorization unit configured to perform QR factorization operation one by one on the left sub panel and the right sub panel with the plurality of accelerators; a sub panel triangular factor computing unit configured to compute the triangular factor of the left sub panel based on the result of the QR factorization operation on the left sub panel after the QR factorization operation on the left sub panel is completed; and a sub panel updating unit configured to update the data of the right sub panel by using the left sub panel and the triangular factor of the left sub panel; wherein the sub panel QR factorization unit performs the QR factorization operation on updated right sub panel. ### Claim 11 (depends on 10) The apparatus according to claim 10, further comprising: a triangular factor computing unit configured to, in each iteration, compute the triangular factor of the current processed panel which is the whole of the at least two sub panels after the QR factorization operations on the at least two sub panels are all completed, and a matrix updating unit configured to, in each iteration, update the data of the matrix part on which no iteration operation has been performed in the unprocessed matrix part by using the current processed panel and the triangular factor of the current processed panel.