Advanced

A Square-Root-Free Matrix Decomposition Method for Energy-Efficient Least Squares Computation on Embedded Systems

Ren, Fengbo; Zhang, Chenxin LU ; Liu, Liang LU ; Xu, Wenyao; Öwall, Viktor LU and Markovic, Dejan (2014) In IEEE Embedded Systems Letters 6(4). p.73-76
Abstract
QR decomposition (QRD) is used to solve least squares (LS) problems for a wide range of applications. However, traditional QR decomposition methods, such as Gram-Schmidt (GS), require high computational complexity and non-linear operations to achieve high throughput, limiting their usage on resource-limited platforms. To enable efficient LS computation on embedded systems for real-time applications, this paper presents an alternative decomposition method, called QDRD, which relaxes system requirements while maintaining the same level of performance. Specifically, QDRD eliminates both the square-root operations in the normalization step and the divisions in the subsequent backward substitution. Simulation results show that the accuracy and... (More)
QR decomposition (QRD) is used to solve least squares (LS) problems for a wide range of applications. However, traditional QR decomposition methods, such as Gram-Schmidt (GS), require high computational complexity and non-linear operations to achieve high throughput, limiting their usage on resource-limited platforms. To enable efficient LS computation on embedded systems for real-time applications, this paper presents an alternative decomposition method, called QDRD, which relaxes system requirements while maintaining the same level of performance. Specifically, QDRD eliminates both the square-root operations in the normalization step and the divisions in the subsequent backward substitution. Simulation results show that the accuracy and reliability of factorization matrices can be significantly improved by QDRD, especially when executed on precision-limited platforms. Furthermore, benchmarking results on an embedded platform show that QDRD provides constantly better energy-efficiency and higher throughput than GS-QRD in solving LS problems. Up to 4 and 6.5 times improvement in energy-efficiency and throughput respectively can be achieved for small-size problems. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
QR decomposition, least squares problem, matrix factorization, computational complexity, energy efficiency
in
IEEE Embedded Systems Letters
volume
6
issue
4
pages
73 - 76
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:84913532509
ISSN
1943-0663
DOI
10.1109/LES.2014.2350997
project
HiPEC
language
English
LU publication?
yes
id
15394723-7fdd-425b-8bb2-a672a189c1d8 (old id 4619001)
date added to LUP
2014-09-04 12:13:02
date last changed
2017-10-22 04:10:21
@article{15394723-7fdd-425b-8bb2-a672a189c1d8,
  abstract     = {QR decomposition (QRD) is used to solve least squares (LS) problems for a wide range of applications. However, traditional QR decomposition methods, such as Gram-Schmidt (GS), require high computational complexity and non-linear operations to achieve high throughput, limiting their usage on resource-limited platforms. To enable efficient LS computation on embedded systems for real-time applications, this paper presents an alternative decomposition method, called QDRD, which relaxes system requirements while maintaining the same level of performance. Specifically, QDRD eliminates both the square-root operations in the normalization step and the divisions in the subsequent backward substitution. Simulation results show that the accuracy and reliability of factorization matrices can be significantly improved by QDRD, especially when executed on precision-limited platforms. Furthermore, benchmarking results on an embedded platform show that QDRD provides constantly better energy-efficiency and higher throughput than GS-QRD in solving LS problems. Up to 4 and 6.5 times improvement in energy-efficiency and throughput respectively can be achieved for small-size problems.},
  author       = {Ren, Fengbo and Zhang, Chenxin and Liu, Liang and Xu, Wenyao and Öwall, Viktor and Markovic, Dejan},
  issn         = {1943-0663},
  keyword      = {QR decomposition,least squares problem,matrix factorization,computational complexity,energy efficiency},
  language     = {eng},
  number       = {4},
  pages        = {73--76},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Embedded Systems Letters},
  title        = {A Square-Root-Free Matrix Decomposition Method for Energy-Efficient Least Squares Computation on Embedded Systems},
  url          = {http://dx.doi.org/10.1109/LES.2014.2350997},
  volume       = {6},
  year         = {2014},
}