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

作者: Juan Luis Jerez , George A. Constantinides , Eric C. Kerrigan

DOI: 10.1109/TC.2013.162

关键词:

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

参考文章(42)
Abid Rafique, Nachiket Kapre, George A. Constantinides, A High Throughput FPGA-Based Implementation of the Lanczos Method for the Symmetric Extremal Eigenvalue Problem Lecture Notes in Computer Science. pp. 239- 250 ,(2012) , 10.1007/978-3-642-28365-9_20
W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem Quarterly of Applied Mathematics. ,vol. 9, pp. 17- 29 ,(1951) , 10.1090/QAM/42792
Leonardo de Moura, Nikolaj Bjørner, Z3: an efficient SMT solver tools and algorithms for construction and analysis of systems. pp. 337- 340 ,(2008) , 10.1007/978-3-540-78800-3_24
A. Benedetti, P. Perona, Bit-width optimization for configurable DSP's by multi-interval analysis asilomar conference on signals, systems and computers. ,vol. 1, pp. 355- 359 ,(2000) , 10.1109/ACSSC.2000.910977
George A. Constantinides, Tutorial paper: Parallel architectures for model predictive control european control conference. pp. 138- 143 ,(2009) , 10.23919/ECC.2009.7074393
K.D. Underwood, K.S. Hemmert, Closing the gap: CPU and FPGA trends in sustainable floating-point BLAS performance field-programmable custom computing machines. pp. 219- 228 ,(2004) , 10.1109/FCCM.2004.21
John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach ,(1989)
Jan Marian Maciejowski, Predictive Control With Constraints ,(2001)
James W. Demmel, Applied Numerical Linear Algebra ,(1997)