Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-17
2001-10-16
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S250000
Reexamination Certificate
active
06304888
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a high speed numerical integration system and method, and in particular to a high speed numerical integration system and method for converting a multi-dimensional sequence into a one-dimensional characteristic value, and for calculating a weighted average for correction.
2. Related Art
Conventional, well known variance reduction methods for Monte Carlo (MC) calculations using a pseudo-random number are as follows.
Antithetic Variable Method
A random sequence and a sequence having the same absolute value but with an opposite sign are joined together to obtain an antithetic distribution of variables in order to reduce variance.
Moment Matching Method
An average and a variance are acquired from a random sequence that has been generated, and the values of the random numbers being corrected so that an anticipated average and variance are obtained.
Since a generated random number is processed using these methods, a problem concerning the autocoorelation has arisen.
In addition, since according to the moment matching method all the random numbers that have been generated must be stored, this method is not practical for high-order dimensions.
Furthermore, these methods by which the locations of points are altered are not suitable for a sequence, such as an LDS (low-discrepancy sequence) that provides biasless sample points.
SUMMARY OF THE INVENTION
It is, therefore, one object of the present invention to provide a numerical integration system and method suitable for a high-order dimensional Monte Carlo calculation.
It is another object of the present invention to provide a numerical integration system and method for acquiring a characteristic in accordance with an integration model and for optimizing the characteristic.
It is an additional object of the present invention to provide a numerical integration system and method as a suitable variance reduction method for an LDS (low-discrepancy sequence).
It is a further object of the present invention to provide a numerical integration system and method for correcting the shape of the distribution of a random number sequence.
It is still another object of the present invention to provide a numerical integration system and method that do not require a large memory capacity for the execution of an integration calculation.
To achieve the above objects: a multi-dimensional sequence is converted into a one-dimensional value; the conversion is optimized in accordance with characteristics of a model; a summation calculation is corrected by using an averaged weight, instead of correcting the values of a random sequence; a histogram is prepared to correct the overall shape of the distribution of a random number sequence; and a sum is calculated for each group of the histogram.
By employing these steps, the convergence speed is increased without sacrificing the calculation time.
Assume that a value of a multi-dimensional integrand is acquired by using a multi-dimensional random number. A set of random numbers required for acquiring one numerical value is called a scenario. According to the conventional Monte Carlo method, this operation is repeated N times and the average for N obtained numerical values is calculated to perform integration of the function.
During each operation, a one-dimensional value is calculated using the multi-dimensional random number. It is preferable that the one-dimensional value matches the characteristic of an integrand.
The one-dimensional values are sorted into several groups, and the appearance frequency for each group is recorded. In addition, the sum of the integrand values corresponding to the current multi-dimensional random numbers is also recorded for each group.
After this process has been repeated N times, a ratio of the recorded appearance frequency to the distribution of one-dimensional values that is theoretical expected for each group is recorded as the weight for a group. For example, assume that a multi-dimensional random number that is consonant with the normal distribution is employed and that its one-dimensional value equals the sum of the individual elements. Since the one-dimensional value is again consonant with the normal distribution, the theoretical distribution can be easily calculated.
Finally, a product of the summation of integrand values and the weight is calculated for each group to obtain the sum for the individual group. This sum is divided by the sum of the weights of all the groups, and the integration value employing the corrected Monte Carlo calculation can be obtained.
REFERENCES:
patent: 5031134 (1991-07-01), Kaplan et al.
patent: 5790442 (1998-08-01), Ninomiya et al.
patent: 5940810 (1999-08-01), Traub et al.
patent: 5949876 (1999-09-01), Ginter et al.
patent: 6208738 (2001-03-01), Goldenfeld et al.
Drumheller Ronald L.
International Business Machines - Corporation
Mai Tan V.
LandOfFree
High speed numerical integration method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed numerical integration method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed numerical integration method and system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2587496