Improved parallel QR method for large least squares problems involving Kronecker products

AbstractA new algorithm is presented for the efficient solution of large least squares problems in which the coefficient matrix of the linear system is a Kronecker product of two smaller dimension matrices. The solution algorithm is based on QR factorizations of the smaller dimension matrices. Near perfect load balancing is achieved by exploiting a ‘commutativity’ property of the Kronecker product, and communication requirements are minimized by employing a binary exchange algorithm for matrix transposition. The parallel algorithm is presented, and timing results are shown from test runs on an Intel i860 computer