Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

A Low Complexity Scaling Method for the Lanczos Kernel in Fixed-Point Arithmetic

Author(s):

J.L. Jerez, G. Constantinides, E.C. Kerrigan
Conference/Journal:

IEEE Transactions on Computers, vol. 64, no. 2, pp. 303-315
Abstract:

We consider the problem of enabling fixed-point implementation of linear algebra kernels on low cost embedded systems, as well as motivating more efficient computational architectures for scientific applications. Fixed-point arithmetic presents additional design challenges compared to floating-point arithmetic, such as having to bound peak values of variables and control their dynamic ranges. Algorithms for solving linear equations or finding eigenvalues are typically nonlinear and iterative, making solving these design challenges a non-trivial task. For these types of algorithms the bounding problem cannot be automated by current tools. We focus on the Lanczos iteration, the heart of well-known methods such as conjugate gradient and minimum residual. We show how one can modify the algorithm with a low complexity scaling procedure to allow us to apply standard linear algebra to derive tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behaviour of fixed-point implementations of the modified problem can be chosen to be at least as good as a floating-point implementation, if necessary. The approach is evaluated on FPGA platforms, highlighting orders of magnitude potential performance and efficiency improvements by moving form floating-point to fixed-point computation.

Year:

2015
Type of Publication:

(01)Article
Supervisor:



File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { JerCon:2015:IFA_4687,
    author={J.L. Jerez and G. Constantinides and E.C. Kerrigan},
    title={{A Low Complexity Scaling Method for the Lanczos Kernel in
	  Fixed-Point Arithmetic}},
    journal={IEEE Transactions on Computers},
    year={2015},
    volume={64},
    number={2},
    pages={303--315},
    month=feb,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=4687}
}
Permanent link