The assignee for this patent, patent number 8805911, is
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;
Keywords for this news article include:
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC
Most Popular Stories
- Bently Creates Alabama Small Business Commission
- When to Say No to Investors, Yes to Mentors
- Bolivar Appointed to NSHMBA National Board
- Rosneft Growth Slowed by Western Sanctions
- SBA Kicks off Hispanic Heritage Month
- Duke Energy, Strata Partner on Big Solar Project
- Lindsay Lohan Claims She Handled Whitney Houston's Body Bag
- Ukraine Offers Temporary Autonomy to Rebel-held Areas
- Thousands Risk Losing Health Care Aid
- Cat Stevens Touring U.S., First Since 1970s