Combined fast multipole-QR compression technique for solving electrically small to large structures for broadband applications

• US 7,933,944 B2
• Filed: 07/16/2007
• Issued: 04/26/2011
• Est. Priority Date: 07/14/2006
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Jandhyala, Vikram, Chowdhury, Indranil
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/778,369
• Publication Number:
  US 20080027689A1
• Time in Patent Office: 1,380 Days
• Field of Search: 708/446
• US Class Current: 708/446
• CPC Class Codes: G06F 2111/10 Numerical modelling
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30

Abstract

An approach that efficiently solves for a desired parameter of a system or device that can include both electrically large fast multipole method (FMM) elements, and electrically small QR elements. The system or device is setup as an oct-tree structure that can include regions of both the FMM type and the QR type. An iterative solver is then used to determine a first matrix vector product for any electrically large elements, and a second matrix vector product for any electrically small elements that are included in the structure. These matrix vector products for the electrically large elements and the electrically small elements are combined, and a net delta for a combination of the matrix vector products is determined. The iteration continues until a net delta is obtained that is within predefined limits. The matrix vector products that were last obtained are used to solve for the desired parameter.

Claims

1. A machine-implemented method for efficiently solving for a desired parameter of a system or device that includes either or both electrically large elements operating at relatively higher frequencies, and electrically small elements operating at relatively lower frequencies, comprising the steps of:

(a) setting up the system or device as a predefined structure that enables a solution for the desired parameter to be determined, the predefined structure including a plurality of elements, wherein the plurality of elements include;

(i) electrically large elements, but not electrically small elements;

or

(ii) electrically small elements, but not electrically large elements;

or

(iii) both electrically large elements and electrically small elements;

(b) executing an iterative solver that determines a first matrix vector product for any electrically large elements, and a second matrix vector product for any electrically small elements that are included in the system or device;

(c) logically combining the matrix vector products for the electrically large elements and the electrically small elements, and determining a net delta for a combination of the matrix vector products;

(d) iteratively repeating steps (b) and (c) as necessary, until a subsequent net delta has been determined that is within a predefined limit;

(f) once a subsequent net delta has been determined that is within the predefined limit, employing said matrix vector products that were last determined to obtain a solution for the desired parameter; and

(g) presenting the solution for the desired parameter to a user in a tangible form.

2. The method of claim 1, wherein the step of setting up the system or device as a predefined structure comprises the step of dividing the system or device into an oct-tree structure.

3. The method of claim 2, wherein the step of dividing the system or device into an oct-tree structure comprises the steps of:

(a) enclosing the system or device with a cube at an 0th level;

(b) splitting the cube at the 0th level into eight child cubes, forming cubes at a 1st level;

(c) recursively repeating the splitting process for cubes at successive levels until a desired number of levels are created; and

(d) for each cube thus formed, maintaining neighbor lists and interaction lists.

4. The method of claim 3, wherein the plurality of elements comprises regions of the oct-tree structure that include one or more cubes, the step of setting up further comprising the step of determining whether each region of the oct-tree structure is an electrically large element or an electrically small element, the electrically large elements being of a fast multipole method (FMM) type, and the electrically small elements being of a QR type.

5. The method of claim 4, wherein the step of setting up the system or device further comprises the step of setting up FMM operators for any of the elements that are of the FMM type, to enable the matrix vector products to be determined.

6. The method of claim 5, wherein the step of setting up the system or device further comprises the step of setting up QR interactions for any of the elements that are of the QR type, to enable the matrix vector products to be determined.

7. The method of claim 5, wherein the step of setting up the FMM operators comprises the step of forming aggregation and disaggregation operators.

8. The method of claim 4, wherein the step of determining whether each region of the oct-tree structure is an electrically large element or an electrically small element comprises the step of determining that a level of the oct-tree structure is an FMM level if an electrical size of the cubes at said level is greater than a defined cutoff value, and that the level of the oct-tree structure is a QR level if the electrical size of the cubes at said level is not greater than the defined cutoff value.

9. The method of claim 8, wherein cubes of an FMM level interact via FMM operators, and for a QR level, contributions of an interaction list for the cubes of the QR level can be compressed.

10. The method of claim 3, wherein the step of determining a second matrix product comprises the step of performing matrix-vector products using QR compressed interaction matrices.

11. A non-transitory memory medium on which machine readable and executable instructions are stored, for carrying out the steps of claim 1.

12. Apparatus for efficiently solving for a desired parameter of a system or device that includes either or both electrically large elements operating at relatively higher frequencies, and electrically small elements operating at relatively lower frequencies, comprising:

(a) a memory for storing machine executable instructions;

(b) a user interface that enables input and output; and

(c) a processor that is coupled to the memory and to the user interface, the processor executing the machine executable instructions to carry out a plurality of functions, including;

(i) setting up the system or device as a predefined structure that enables a solution for the desired parameter to be determined, the predefined structure including a plurality of elements, wherein the plurality of elements include;

(1) electrically large elements, but not electrically small elements;

or

(2) electrically small elements, but not electrically large elements;

or

(3) both electrically large elements and electrically small elements;

(ii) executing an iterative solver that determines a first matrix vector product for any electrically large elements, and a second matrix vector product for any electrically small elements that are included in the system or device;

(iii) logically combining the matrix vector products for the electrically large elements and the electrically small elements, and determining a net delta for a combination of the matrix vector products;

(iv) iteratively repeating steps (b) and (c) as necessary, until a subsequent net delta has been determined that is within a predefined limit;

(v) once a subsequent net delta has been determined that is within the predefined limit, employing said matrix vector products that were last determined to obtain a solution for the desired parameter; and

(vi) presenting the solution for the desired parameter to a user in a tangible form.

13. The apparatus of claim 12, wherein the machine executable instructions cause the processor to divide the system or device into an oct-tree structure.

14. The apparatus of claim 13, wherein the machine executable instructions cause the processor to divide the system or device into the oct-tree structure by:

(a) enclosing the system or device with a cube at a 0th level;

(b) splitting the cube at the 0th level into eight child cubes, forming cubes at a 1st level;

(c) recursively repeating the splitting process for cubes at successive levels until a desired number of levels are created; and

(d) for each cube thus formed, maintaining neighbor lists and interaction lists.

15. The apparatus of claim 14, wherein the plurality of elements comprises regions of the oct-tree structure that include one or more cubes, and wherein the machine executable instructions further cause the processor to determining whether each region of the oct-tree structure is an electrically large element or an electrically small element, the electrically large elements being of a fast multipole method (FMM) type, and the electrically small elements being of a QR type.

16. The apparatus of claim 15, wherein the machine executable instructions cause the processor to setup FMM operators for any of the elements that are of the FMM type, to enable the matrix vector products to be determined.

17. The apparatus of claim 16, wherein the machine executable instructions cause the processor to setup QR interactions for any of the elements that are of the QR type, to enable the matrix vector products to be determined.

18. The apparatus of claim 16, wherein the machine executable instructions cause the processor to form aggregation and disaggregation operators.

19. The apparatus of claim 15, wherein the machine executable instructions cause the processor to determine whether each region of the oct-tree structure is an electrically large element or an electrically small element by determining that a level of the oct-tree structure is an FMM level if an electrical size of the cubes at said level are greater than a defined cutoff value, and that the level of the oct-tree structure is a QR level if the electrical size of the cubes at said level are not greater than the defined cutoff value.

20. The apparatus of claim 19, wherein cubes of an FMM level interact via FMM operators, and for a QR level, contributions of an interaction list for the cubes of the QR level can be compressed.

21. The apparatus of claim 14, wherein the machine executable instructions cause the processor to determine a second matrix vector product by performing matrix-vector products using QR compressed interaction matrices.