US 9,176,931 B2Granted

Software tool for implementing modified QR decomposition in hardware

AssigneeNational Instruments Corporation

InventorYong Rao

Life of this patent

Estimating the term…

Loading patent…

Abstract

System and method for developing a circuit for QR decomposition with auxiliary functionality. A first function is included in a first program. The first function is configurable to specify an auxiliary function to be performed by a modified QR decomposition circuit in addition to QR decomposition of a matrix A into two matrices Q and R using a Modified Gram Schmidt process. A second program is automatically generated based on configuration of the QR decomposition and the first function. The second program includes program code implementing the QR decomposition and the auxiliary function for the first function in the first program. A hardware configuration program (HCP) may be automatically generated based on the first program, including the second program, where the HCP is deployable to hardware, e.g., a programmable hardware element, thereby implementing the modified QR decomposition circuit, including the QR decomposition of the matrix A and the auxiliary function.

Claims20

Dependent claims

A non-transitory computer accessible memory medium that stores program instructions executable by a processor to implement:

including a first function in a first program in response to user input, wherein the first function is user configurable to specify an auxiliary function to be performed by a modified QR decomposition circuit in addition to QR decomposition of a matrix A into two matrices Q and R using a Modified Gram Schmidt (MGS) process, wherein Q represents an orthonormal basis that spans a column space of A, and wherein R is a triangular matrix;
automatically generating a second program based on a configuration of the QR decomposition and the auxiliary function, wherein the second program comprises program code that implements the QR decomposition and the auxiliary function for the first function in the first program;
and
automatically generating a hardware configuration program based on the first program, including the second program, wherein the hardware configuration program is deployable to programmable hardware, thereby implementing the modified QR decomposition circuit, including the QR decomposition of the matrix A and the auxiliary function;
wherein the hardware configuration program specifies that the modified QR decomposition circuit comprise:
an input;
a first set of hardware components, coupled to the input, wherein the first set of hardware components are dedicated to computing matrix Q;
and
an output;
wherein the input is configured to:
receive a first set of inputs at the input, wherein the first set of inputs includes the matrix A and a scaling factor σ;
wherein the first set of hardware components is configured to:
compute matrix Q based on the first set of inputs using the MGS process;
scale an identity matrix I by the scaling factor σ, thereby generating scaled identity matrix σI;
receive a second set of inputs, wherein the second set of inputs is different from the first set of inputs, and wherein the second set of inputs comprises the scaled identity matrix;
compute scaled matrix σR−1 based on the second set of inputs using the MGS process;
unscale the scaled matrix σR−1, thereby computing matrix R−1, wherein matrix R−1 is the inverse of matrix R;
and
wherein the output is configured to:
output the matrix Q and/or matrix R−1 via the output.

17 more elements

A method, comprising:

utilizing a computer to perform:
including a first function in a first program in response to user input, wherein the first function is user configurable to specify an auxiliary function to be performed by a modified QR decomposition circuit in addition to QR decomposition of a matrix A into two matrices Q and R using a Modified Gram Schmidt (MGS) process, wherein Q represents an orthonormal basis that spans a column space of A, and wherein R is a triangular matrix;
automatically generating a second program based on a configuration of the QR decomposition and the auxiliary function, wherein the second program comprises program code that implements the QR decomposition and the auxiliary function for the first function in the first program;
and
automatically generating a hardware configuration program based on the first program, including the second program, wherein the hardware configuration program is deployable to programmable hardware, thereby implementing the modified QR decomposition circuit, including the QR decomposition of the matrix A and the auxiliary function;
wherein the hardware configuration program specifies that the modified QR decomposition circuit comprise:
an input;
a first set of hardware components, coupled to the input, wherein the first set of hardware components are dedicated to computing matrix Q;
and
an output;
wherein the input is configured to:
receive a first set of inputs at the input, wherein the first set of inputs includes the matrix A and a scaling factor σ;
wherein the first set of hardware components is configured to:
compute matrix Q based on the first set of inputs using the MGS process;
scale the identity matrix by the scaling factor σ, thereby generating scaled identity matrix σI;
receive a second set of inputs, wherein the second set of inputs is different from the first set of inputs, and wherein the second set of inputs comprises the scaled identity matrix;
compute scaled matrix σR−1 based on the second set of inputs using the MGS process;
unscale the scaled matrix σR−1, thereby computing matrix R−1, wherein matrix R−1 is the inverse of matrix R;
and
wherein the output is configured to:
output the matrix Q and/or matrix R−1 via the output.

18 more elements

A non-transitory computer accessible memory medium that stores program instructions executable by a processor to implement:

including a first function in a first program in response to user input, wherein the first function is user configurable to specify an auxiliary function to be performed by a modified QR decomposition circuit in addition to QR decomposition of a matrix A into two matrices Q and R using a Modified Gram Schmidt (MGS) process, wherein Q represents an orthonormal basis that spans a column space of A, and wherein R is a triangular matrix;
automatically generating a second program based on a configuration of the QR decomposition and the auxiliary function, wherein the second program comprises program code that implements the QR decomposition and the auxiliary function for the first function in the first program;
and
automatically generating a hardware configuration program based on the first program, including the second program, wherein the hardware configuration program is deployable to programmable hardware, thereby implementing the modified QR decomposition circuit, including the QR decomposition of the matrix A and the auxiliary function;
wherein the hardware configuration program specifies that the modified QR decomposition circuit comprise:
an input;
a first set of hardware components, coupled to the input, wherein the first set of hardware components are dedicated to computing matrix Q;
and
an output;
wherein the input is configured to:
receive a first set of inputs at the input, wherein the first set of inputs includes the matrix A;
wherein the first set of hardware components is configured to:
compute matrix Q based on the first set of inputs using the MGS process;
receive a second set of inputs, wherein the second set of inputs is different from the first set of inputs, and wherein the second set of inputs comprises an identity matrix;
compute matrix R−1 based on the second set of inputs using the MGS process, wherein matrix R−1 is the inverse of matrix R;
and
wherein the output is configured to:
output the matrix Q and/or matrix R−1 via the output.

15 more elements

A method, comprising:

utilizing a computer to perform:
including a first function in a first program in response to user input, wherein the first function is user configurable to specify an auxiliary function to be performed by a modified QR decomposition circuit in addition to QR decomposition of a matrix A into two matrices Q and R using a Modified Gram Schmidt (MGS) process, wherein Q represents an orthonormal basis that spans a column space of A, and wherein R is a triangular matrix;
automatically generating a second program based on a configuration of the QR decomposition and the auxiliary function, wherein the second program comprises program code that implements the QR decomposition and the auxiliary function for the first function in the first program;
and
automatically generating a hardware configuration program based on the first program, including the second program, wherein the hardware configuration program is deployable to programmable hardware, thereby implementing the modified QR decomposition circuit, including the QR decomposition of the matrix A and the auxiliary function;
wherein the hardware configuration program specifies that the modified QR decomposition circuit comprise:
an input;
a first set of hardware components, coupled to the input, wherein the first set of hardware components are dedicated to computing matrix Q;
and
an output;
wherein the input is configured to:
receive a first set of inputs at the input, wherein the first set of inputs includes the matrix A;
wherein the first set of hardware components is configured to:
compute matrix Q based on the first set of inputs using the MGS process;
receive a second set of inputs, wherein the second set of inputs is different from the first set of inputs, and wherein the second set of inputs comprises an identity matrix;
compute matrix σR−1 based on the second set of inputs using the MGS process, wherein matrix R−1 is the inverse of matrix R;
and
wherein the output is configured to:
output the matrix Q and/or matrix R−1 via the output.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/941,275Filed 12 Jul 2013 · continuation in part
Priority: 30 Jan 2013
Published: US 2014/0214910 A131 Jul 2014
Granted: 3 Nov 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification2 codes

G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
G06F
Computing and data processing

Family

Application61/758,357Us provisional application · filed 30 Jan 2013
Application13/865,357Parent of this continuation-in-part · filed 18 Apr 2013
US 2014/0214911 A1Pre-grant publication · published 31 Jul 2014
US 2014/0214910 A1Published application
US 9,201,849 B2Related patent
US 9,176,931 B2This patent

From the US filing history. Foreign family members aren’t listed.