News Column

Patent Issued for Cholesky Decomposition in an Integrated Circuit Device

August 27, 2014



By a News Reporter-Staff News Editor at Journal of Engineering -- According to news reporting originating from Alexandria, Virginia, by VerticalNews journalists, a patent by the inventors Xu, Lei (High Wycombe, GB); Langhammer, Martin (Salisbury, GB), filed on May 31, 2011, was published online on August 12, 2014.

The assignee for this patent, patent number 8805911, is Altera Corporation (San Jose, CA).

Reporters obtained the following quote from the background information supplied by the inventors: "Certain matrix operations require that a matrix be factored. For example, factoring a matrix may be necessary when a matrix is to be inverted. The result may be a 'triangulated' matrix--i.e., a matrix with zero values above the diagonal. The consequence is that only the values on the diagonal, and in the columns below those values, need to be calculated.

"In Cholesky decomposition, to factor an input matrix A, an element L.sub.i,i of the diagonal of the resultant triangulated matrix M, may be calculated as:

".times. ##EQU00001## where a.sub.i,i is the i,i.sup.th element of the original input matrix A, and L.sub.i,k is the i,k.sup.th element in the resultant triangulated matrix M. The subsequent elements in the j.sup.th column of M may be calculated as:

".times..times..times..times.> ##EQU00002## where a.sub.i,j is the i,j.sup.th element of the original matrix input A, and L.sub.i,k and L.sub.j,k are the i,k.sup.th and j,k.sup.th elements, respectively, in the resultant triangulated matrix M. To perform this calculation, the L.sub.j,j term needs to be calculated before any of the L.sub.i,j (i>j) elements can be calculated. The inner product in each term (i.e., .SIGMA..sub.k=1.sup.j-1L.sub.i,kL.sub.i,k or .SIGMA..sub.k=1.sup.j-1L.sub.i,kL.sub.j,k)--which, in the case of all real values is the same as a dot product, but in the case of complex values requires computing complex conjugates--may require dozens of clock cycles. Similarly, the square root calculation in the computation of L.sub.i,j can also impose noticeable latency.

"Moreover, different Cholesky decomposition implementations may need to accommodate different matrix sizes or satisfy different throughput requirements. This may particularly be the case in programmable devices, where different users may require resources for matrix operations of different sizes or at different speeds."

In addition to obtaining background information on this patent, VerticalNews editors also obtained the inventors' summary information for this patent: "The present invention relates to efficient and flexible circuitry for implementing Cholesky decomposition. A programmable integrated circuit device such as a programmable logic device (PLD) may be used to implement the Cholesky decomposition circuitry.

"In accordance with embodiments of the present invention, there is provided circuitry for performing matrix decomposition operable to triangulate an input matrix to create a resultant triangulated matrix. The circuitry for performing matrix decomposition includes a plurality of processing elements of a first type for outputting respective elements of the resultant matrix. The circuitry for performing matrix decomposition also includes a plurality of processing elements of a second type, coupled to outputs of the plurality of processing elements of the first type, for outputting respective product elements corresponding to respective elements of said resultant matrix. Each one of the processing elements of the second type includes a first computation path and a second computation path. The first computation path is operable to add/subtract a product of respective first and second elements of the resultant matrix from a respective element of the input matrix to output a respective product difference element. The second computation path is configurable to combine respective third, fourth, fifth, and sixth elements of the resultant matrix to output a respective inner product element.

"A method of configuring such circuitry on a programmable device, a programmable device so configurable, and a machine-readable data storage medium encoded with software for performing the method, are also provided."

For more information, see this patent: Xu, Lei; Langhammer, Martin. Cholesky Decomposition in an Integrated Circuit Device. U.S. Patent Number 8805911, filed May 31, 2011, and published online on August 12, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8805911.PN.&OS=PN/8805911RS=PN/8805911

Keywords for this news article include: Altera Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Journal of Engineering


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters