# US 7,610,323 B2 · Method and apparatus for initializing interval computations through subdomain sampling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,610,323 B2
- Document ID: US7610323B2
- Status: Granted
- Kind: B2
- Application number: 11/325,214
- Filed: 2006-01-03
- Published: 2007-07-05
- Granted: 2009-10-27
- Earliest claimed: 2006-01-03
- Assignees: Sun Microsystems, Inc.
- Inventors: Gregory R. Ruetsch
- Web page: https://patentgrep.com/patent/US7610323B2

## CPC

- G06F 7/49989: {Interval arithmetic}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

One embodiment of the present invention provides a system that uses a computer to evaluate a function within a domain using an interval computing technique. During operation, the system receives the function and the domain over which the function is to be evaluated. Next, the system creates a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain. The system then performs evaluations on the set of sampling subdomains to generate evaluation results. Next, the system sorts the evaluation results based on box size. The system then selects a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results. The system next discretizes the domain into subdomains of the selected box size. Finally, the system uses the interval computing technique to evaluate the function on each of the subdomains wherein the interval computing technique recursively subdivides and evaluates the function on the subdomains.

## Claims

### Claim 1

A method for using a computer system to evaluate a function within a domain using an interval computing technique, the method comprising:
receiving the function and the domain over which the function is to be evaluated;
creating a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;
performing evaluations on the set of sampling subdomains to generate evaluation results;
sorting the evaluation results based on box size;
selecting a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;
discretizing the domain into subdomains of the selected box size; and
using the interval computing technique to evaluate the function on each of the subdomains wherein the interval computing technique recursively subdivides and evaluates the function on the subdomains.

### Claim 2 (depends on 1)

The method of claim 1, wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

### Claim 3 (depends on 1)

The method of claim 1, wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

### Claim 4 (depends on 1)

The method of claim 1, wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

### Claim 5 (depends on 1)

The method of claim 1, wherein performing evaluations on the set of sampling subdomains involves:
evaluating the function on the set of sampling subdomains; and
evaluating derivatives of the function on the set of sampling subdomains.

### Claim 6 (depends on 1)

The method of claim 1, wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:
box consistency;
Hull consistency;
term consistency;
monotonicity; and
Newton contraction.

### Claim 7 (depends on 6)

The method of claim 6, wherein the evaluation results indicate an initial box size on which a specific interval technique becomes effective for function evaluation.

### Claim 8

A computer-readable storage medium storing instructions that when executed by a computer system cause the computer system to use a computer system to evaluate a function within a domain using an interval computing technique, the method comprising:
receiving the function and the domain over which the function is to be evaluated;
creating a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;
performing evaluations on the set of sampling subdomains to generate evaluation results;
sorting the evaluation results based on box size;
selecting a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;
discretizing the domain into subdomains of the selected box size; and
using the interval computing technique to evaluate the function on each of the subdomains wherein the interval computing technique recursively subdivides and evaluates the function on the subdomains.

### Claim 9 (depends on 8)

The computer-readable storage medium of claim 8, wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

### Claim 10 (depends on 8)

The computer-readable storage medium of claim 8, wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

### Claim 11 (depends on 8)

The computer-readable storage medium of claim 8, wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

### Claim 12 (depends on 8)

The computer-readable storage medium of claim 8, wherein performing evaluations on the set of sampling subdomains involves:
evaluating the function on the set of sampling subdomains; and
evaluating derivatives of the function on the set of sampling subdomains.

### Claim 13 (depends on 8)

The computer-readable storage medium of claim 8, wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:
box consistency;
Hull consistency;
term consistency;
monotonicity; and
Newton contraction.

### Claim 14 (depends on 13)

The computer-readable storage medium of claim 13, wherein the evaluation results indicate an initial box size on which a specific interval technique becomes effective for function evaluation.

### Claim 15

An apparatus that uses a computer system to evaluate a function within a domain using an interval computing technique, the apparatus comprising:
a receiving mechanism configured to receive the function and the domain over which the function is to be evaluated;
a memory for storing the function and the domain;
a generation mechanism configured to create a set of sampling subdomains within the domain by generating a set of boxes of different sizes which are located at different positions across the domain;
an evaluation mechanism configured to perform evaluations on the set of sampling subdomains to generate evaluation results;
a sorting mechanism configured to sort the evaluation results based on box size;
a selection mechanism configured to select a box size from the different box sizes by identifying a largest box size which achieves tight bounds on the evaluation results;
a discretization mechanism configured to discretize the domain into subdomains of the selected box size; and
an evaluation mechanism configured to use the interval computing technique to evaluate the function on each of the subdomains by recursively subdividing and evaluating the function on the subdomains.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the tight bound is obtained at a box size where subsequent reductions in box size decrease the percentage of boxes that contain a solution by less than a pre-specified amount.

### Claim 17 (depends on 15)

The apparatus of claim 15, wherein the sampling subdomains include large sampling subdomains which do not generate tight bounds on the evaluation results.

### Claim 18 (depends on 15)

The apparatus of claim 15, wherein identifying the largest box size which achieves tight bounds on the evaluation results involves identifying a transition from a sampling subdomain size which does not generate tight bounds on the evaluation results to a next-largest sampling subdomain size which generates tight bounds.

### Claim 19 (depends on 15)

The apparatus of claim 15, wherein performing evaluations on the set of sampling subdomains involves:
evaluating the function on the set of sampling subdomains; and
evaluating derivatives of the function on the set of sampling subdomains.

### Claim 20 (depends on 15)

The apparatus of claim 15, wherein performing evaluations on the set of sampling subdomains further involves using interval techniques, which can include:
box consistency;
Hull consistency;
term consistency;
monotonicity; and
Newton contraction.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the evaluation results on the sampling subdomains indicate an initial box size on which a specific interval technique becomes effective for function evaluation.