Skip to main content
SpringerLink
Log in
Book cover

Advances in Real-Time Systems pp 41–81Cite as

Large-Scale Linear Computations with Dedicated Real-Time Architectures

  • Chapter
  • First Online:

  • 1258 Accesses

Abstract

Understanding the connection between algorithms and solvers for large scale systems on the one hand, and appropriate architectures that execute them efficiently on the other is key to the effective design of modern signal processing applications. This trend has started with the emergence of digital media, large scale signal processing for image coding and analysis, digital mobile telephony and digital processing in medical imaging. In many cases dedicated, hardware or software dominated methods on a single processor have been used, only in recent times more generic methods based on general purpose array architectures, either dedicated to media processing or for general computing have become realizable. Massive use of parallelism becomes attractive and should, in the future, allow us to tackle large scale problems in a streamlined fashion.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD   109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

References

  1. Ahmed HM, Delosme J-M, Morf M (1982) Highly concurrent computing structures for matrix arithmetic and signal processing. IEEE Comp 15(1):65–86

    Article  Google Scholar 

  2. Björck A (1996) Numerical methods for least squares problems. SIAM, Philadelphia, PA

    Book  MATH  Google Scholar 

  3. Bolz J, Farmer I, Grinspun E, Schröder P (2003) Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. In: SIGGRAPH 2003, ACM, New York, pp 917–924

    Google Scholar 

  4. Chandrasekaran S, Dewilde P, Gu M, Pals T, van der Veen A-J, Xia J (2002) A fast backward stable solver for sequentially semi-separable matrices, volume HiPC202 of Lecture notes in computer science, Springer, Berlin, pp 545–554

    Google Scholar 

  5. Dewilde P (1988) New algebraic methods for modelling large-scale integrated circuits. Int J Circ Theory Appl 16(4):473–503

    Article  MATH  Google Scholar 

  6. Dewilde P, van der Veen A-J (1998) Time-varying systems and computations. Kluwer, Dordrecht

    Book  MATH  Google Scholar 

  7. Dewilde P, van der Veen A-J (2000) Inner-outer factorization and the inversion of locally finite systems of equations. Linear Algebra Appl 313:53–100

    Article  MathSciNet  MATH  Google Scholar 

  8. Dewilde P, Diepold K, Bamberger W (2004a) Optic flow computation and time-varying system theory. In: Proceedings of the international symposium on mathematical theory of networks and systems (MTNS). Katholieke Universiteit Leuven, Belgium

    Google Scholar 

  9. Dewilde P, Diepold K, Bamberger W (2004b) A semi-separable approach to a tridiagonal hierarchy of matrices with applications to image analysis. In: Proceedings of the international symposium on mathematical theory of networks and systems (MTNS). Katholieke Universiteit Leuven, Belgium

    Google Scholar 

  10. Durkovic M, Zwick M, Obermeier F, Diepold K (2006) Performance of optical flow techniques on graphics hardware. In: IEEE international conference on multimedia and expo (ICME)

    Book  Google Scholar 

  11. Fadeeva VN (1959) Computational methods of linear algebra. Dover, New York

    Google Scholar 

  12. Gastona FMF, Irwina GW (1989) Systolic approach to square root information kalman filtering. Int J Control 50(1):225–248

    Article  MathSciNet  Google Scholar 

  13. Gohberg I, Kailath T, Koltracht I (1985) Linear complexity algorithms for semiseparable matrices. Integral Equations Operator Theory 8:780–804

    Article  MathSciNet  MATH  Google Scholar 

  14. Golub G, van Loan Ch (1989) Matrix computations. John Hopkins University Press, Baltimore, MD

    MATH  Google Scholar 

  15. Götze J, Schwiegelshohn U (1988) Sparse matrix-vector multiplication on a systolic array. In: International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol 4. IEEE, pp 2061–2064

    Google Scholar 

  16. Hartley RI (1997) In defence of the 8-point algorithm. IEEE Trans Pattern Anal Machine Intell 19(6):580–593

    Article  Google Scholar 

  17. Jainandunsing K, Deprettere EF (1989a) A new class of parallel algorithms for solving systems of linear equations. SIAM J Scientific Comput 10(5):880–912

    Article  MathSciNet  MATH  Google Scholar 

  18. Jainandunsing K, Deprettere EdF (1989b) A new class of parallel algorithms for solving, systems of linear equations. SIAM J Sct Stat Comput 10(5):880–912

    Article  MathSciNet  MATH  Google Scholar 

  19. Jean-Marc D, Ipsen Ilse C.F. (1986) Parallel solution of symmetric positive definite systems with hyperbolic rotations. Linear Algebra Appl 77:75–111.

    Article  MathSciNet  MATH  Google Scholar 

  20. Jichun Bu, Deprettere F, Dewilde P (1990) A design methodology for fixed-size systolic arrays. In: Proceedings of the international conference on application specific array processors

    Google Scholar 

  21. Kailath T (1981) Lectures on Wiener and Kalman Filtering. CISM Courses and Lectures No. 140, Springer, Wien, New York

    Google Scholar 

  22. Kailath T, Sayed A (1999) Fast reliable algorithms for matrices with structure. SIAM, Philadelphia, PA

    Book  MATH  Google Scholar 

  23. Kailath T, Sayed A, Hasibi B (2000) Linear esimtation. Prentice Hall, Upper Saddle River, NJ

    Google Scholar 

  24. Kienhuis B e.a. (2010) Hotspot parallelizer. Compaan Design. http://www.compaandesign.com/technology/overview, visitied on Nov.14.2011.

  25. Kronecker L (1890) Algebraische Reduction der schaaren bilinearer Formen. S.B. Akad. Berlin, pp 663–776

    Google Scholar 

  26. Krüger J, Westermann R (2005) Linear algebra operators for gpu implementation of numerical algorithms. In: SIGGRAPH 2005. ACM, New York

    Google Scholar 

  27. Kung SY (1988) VLSI array processors. Prentice Hall, Englewood Cliffs, NJ

    Google Scholar 

  28. Larsson D, Schinner e.a. P (1986) The CADMUS 9230 ICD Graphic Workstation 1, volume The integrated design handbook, chapter 8, Delft University Press, Delft, pp 8.1–8.29

    Google Scholar 

  29. Lucas BD, Kanade T (1981) An iterative image registration technique with an application to stereo vision. In: Proceedings of imaging understanding workshop, pp 121–130

    Google Scholar 

  30. Misraa M, Nassimib D, Prasannaa VK (1993) Efficient vlsi implementation of iterative solutions to sparse linear systems. Parallel Comput 19(5):525–544

    Article  Google Scholar 

  31. Nash JG, Hansen S (1988) Modified faddeeva algorithm for concurrent execution of linear algebraic operations. IEEE Trans Comp 37(2):129–137

    Article  MATH  Google Scholar 

  32. Paige ChC, Saunders MA (1982) LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans Math Softw 8:43–71

    Article  MathSciNet  MATH  Google Scholar 

  33. Polka LA, Kalyanam H, Hu G, Krishnamoorthy S (2007) Package technology to address the memory bandwidth challenge for tera-scale computing. Intel Technol J 11(3):197–206

    Article  Google Scholar 

  34. Proudler IK, McWhirter JG, Shepherd TJ (1991) Computationally efficient qr decomposition approach to least squares adaptive filtering. IEE Proc F, Radar Signal Processing 138(4): 341–353

    Article  Google Scholar 

  35. Schunck BG, Horn BKP (1981) Determining optical flow. Artif Intell 17(1-3):185–203

    MATH  Google Scholar 

  36. Saad Y (2003) Iterative methods for sparse linear systems. SIAM, Philadelphia, PA

    Book  MATH  Google Scholar 

  37. Strang G (2007) Computational science and engineering. Wellesley-Cambridge Press, Wellesley, MA

    MATH  Google Scholar 

  38. Tong L, van der Veen A-J, Dewilde P (2002) A new decorrelating rake receiver for long-code wcdma. In: Proceedings 2002 conference on information sciences systems. Princeton University, NJ

    Google Scholar 

  39. Vanderbril R, van Barel M, Mastronardi N (2008) Matrix computations and semi-separable matrices. John Hopkins University Press, Baltimore, MD

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering and Information Technology, Technische Universität München, München, Germany

    Klaus Diepold

  2. Institute for Advanced Study, Technische Universität München, München, Germany

    Patrick Dewilde

Authors
  1. Patrick Dewilde
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klaus Diepold
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Klaus Diepold .

Editor information

Editors and Affiliations

  1. LS für Realzeit-Computersysteme, TU München, Arcisstraße 21, München, 80290, Germany

    Samarjit Chakraborty

  2. LS Kommunikationsnetze, TU München, Arcisstr. 21, München, 80290, Germany

    Jörg Eberspächer

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Dewilde, P., Diepold, K. (2012). Large-Scale Linear Computations with Dedicated Real-Time Architectures. In: Chakraborty, S., Eberspächer, J. (eds) Advances in Real-Time Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24349-3_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-24349-3_3

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-24348-6

  • Online ISBN: 978-3-642-24349-3

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation