Data processing: measuring – calibrating – or testing – Measurement system – Measured signal processing
Reexamination Certificate
2000-06-08
2002-11-26
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Measured signal processing
C702S189000, C702S109000, C700S052000, C700S280000
Reexamination Certificate
active
06487524
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to system design, and more particularly to improved methods and systems for designing controllable parameters for a system.
BACKGROUND OF THE INVENTION
The solution of a Symmetric Positive Definite (SPD) Toeplitz (or block Toeplitz) linear system of equations is useful in system design. For example, digital filter design may involve the solution of a SPD Toeplitz linear system of equations. Further, the solution of these equations is often involved in designing a digital filter for an active noise and vibration control (ANVC) system.
Methods for solving symmetric positive-definite (SPD) Toeplitz (or block Toeplitz) linear systems of equations may be divided into direct and iterative methods. The direct methods may be further subdivided into classical methods, fast methods, and superfast methods. In the following paragraphs, which discuss these methods, we will refer to the problem of solving a SPD Toeplitz linear system of T equations and unknowns.
Classical direct methods include Gauss elimination as well as the Cholesky procedure which is well-know to be numerically stable even for ill-conditioned linear systems of equations. Unfortunately, because these methods do not exploit the Toeplitz structure, they are fairly slow in that they require O[T
3
] calculations, where O[·] indicates the order of the number of required calculations. Thus, O[T
3
] indicates that the solution takes on the order of T
3
calculations.
The fast direct methods include Levinson-type algorithms, as well as the Schur type algorithms which are associated with displacement theory. Because they exploit the Toeplitz structure, they require only O[T
2
] calculations. Unfortunately, while these are known to be numerically stable for well-conditioned linear systems of equations, they often break down (yielding no solution) for ill-conditioned linear systems of equations.
The superfast direct methods exploit the Toeplitz structure and require only O[T(log T)
2
] calculations. However, these methods are relatively new and little is known regarding their numerical stability for ill-conditioned linear systems of equations.
The principal iterative method is the Conjugate Gradient (CG) method. This method offers good numerical stability and a faster solution than the direct methods. Further, it is flexible and can be applied to various quasi-Toeplitz linear systems of equations. This method has been popular for the solution of sparse linear systems of equations since the work of Hestenes and Steifel in 1952. In principal, the CG method converges to the exact solution in just T iterations. In practice, however, the iterations are stopped to yield an approximate solution after far fewer iterations. The CG method is often used with a preconditioner that serves to accelerate the procedure so that a good approximate solution will be obtained with a few iterations. This CG method using a preconditioner is referred to as the Preconditioned Conjugate Gradient (PCG) method. Although the CG and PCG methods are useful for the solution of sparse linear systems of equations, their computational cost can become quite large for dense linear systems of equations. Accordingly, because of the computational cost involved, the CG and PCG methods have not been popular for dense linear systems of equations.
In 1986, Strang showed how to apply the PCG method in a computationally efficient manner to Toeplitz (or block-Toeplitz) SPD linear systems of equations, despite the fact that these are dense linear systems of equations. By exploiting the Toeplitz structure, Strang's approach could solve a Toeplitz SPD linear system of T equations using only O[T log T] calculations. Moreover, Strang's method appears to remain numerically stable even for poorly-conditioned linear systems of equations. Consequently, Strang's approach has been a method for solving large block-Toeplitz SPD linear systems of equations such as those that arise in the design of a digital filter for a large ANVC system.
Large system design problems, such as the design of a finite impulse response (FIR) digital filter (e.g., with T=1024 taps) for a multiple-input multiple-output ANVC system with many (e.g., M=32) input signals and many (e.g., &eegr;=32) output signals, may involve the solution of a very large block Toeplitz SPD linear system of (e.g., &eegr;MT=1,048,576) equations to determine the very large (e.g., &eegr;MT=1,048,576) number of system parameters. Even with Strang's approach the computational costs for such a system design can be very high and, since high computational costs are reflected in similarly high financial costs, these costs can be economically prohibitive.
As such, there is a need for computationally efficient methods and systems for determining the controllable parameters of a system, wherein this determination involves the solution of a linear system of equations.
SUMMARY OF THE INVENTION
Accordingly, the present invention is directed to methods and systems that obviate the above and other disadvantages of the prior art.
Methods and systems consistent with the present invention include a process for computing a plurality of controllable parameters that affect the operation of a system. This process includes generating a sequence of matrices V(r) using a known system, generating a sequence of matrices S(t) using an input signal, wherein the sequence of matrices V(r) and the sequence of matrices S(t) correspond to a Tensor-Convolution Block-Toeplitz structure, generating a vector b using the input signal and the known system, and generating the plurality of controllable parameters using the sequence of matrices V(r), the sequence of matrices S(t), and the vector b by a process employing a fast matrix-vector multiply.
In another aspect the invention comprises a system, wherein a plurality of controllable parameters that affect the operation of the system are expressible as a vector x, and wherein a constraint relationship related to the controllable parameters, is expressible in the form of a matrix A associated with the controllable parameters, and with a set of constraint limits, b, such that Ax=b. This system includes a memory for storing a sequence of matrices V(r), a sequence of matrices S(t), and a vector b, wherein the sequence of matrices V(r) and the sequence of matrices S(t) correspond to a Tensor Convolution Block Toeplitz structure, wherein the sequence of matrices V(r) is generated using a known system, and wherein the sequence of matrices S(t) is generated using an input signal. This system further includes a processor for determining a plurality of controllable parameters, x, using the sequence of matrices V(r), the sequence of matrices S(t), and the vector b, by a process employing a fast matrix-vector multiply, wherein the vector b is generated using the input signal and the known system.
In yet another aspect the invention comprises a process for determining a plurality of parameters for an unknown system given a known system. This process includes generating a sequence of matrices V(r) using a known system, generating a sequence of matrices S(t) using an input signal, wherein the sequence of matrices V(r) and the sequence of matrices S(t) correspond to a Tensor-Convolution Block-Toeplitz structure, generating a vector b using the input signal and the known system, and generating the plurality of controllable parameters using the sequence of matrices V(r), the sequence of matrices S(t), and the vector b by a process employing a fast matrix-vector multiply.
REFERENCES:
patent: 5420803 (1995-05-01), Judell
patent: 5642195 (1997-06-01), Drachev et al.
patent: 6038197 (2000-03-01), Sitton et al.
patent: 6208739 (2001-03-01), Venugopal et al.
patent: 0712115 (1996-05-01), None
patent: 0814456 (1997-12-01), None
G. Strang, A Proposal for Toeplitz Matrix Calculations, Stud. Apply. Math., 74, 1986, pp. 171-76.
T.F. Chan, An Optimal Circulant Precondition
Barbee Manuel L.
BBNT Solutions LLC
Hoff Marc S.
Suchyta Leonard Charles
Weixel James K.
LandOfFree
Methods and apparatus for designing a system using the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for designing a system using the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for designing a system using the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961704