Abstract: |
Geostatistical modeling involves many variables and many locations. LU simulation is a popular method for generating realizations, but the covariance matrices that describe the relationships between all of these variables are large and not necessarily amenable to direct decomposition, inversion or manipulation. This paper shows a method similar to LU simulation based on singular value decomposition of large covariance matrices for generating unconditional or conditional realizations using randomized methods. The application of randomized methods in generating realizations, by finding eigenvalues and eigenvectors of very large covariance matrices is developed with examples. These methods use random sampling to identify a subspace that captures most of the actions of a matrix by considering the dominant eigenvalues. Usually, not all eigenvalues have to be calculated; the fluctuations can be described almost completely by a few eigenvalues. The first k eigenvalues corresponds to a large amount of energy of the random field with the size of n×n. For a dense input matrix, randomized algorithms require O(nnlog(k)) floating-point operations (flops) in contrast with O(nnk) for classical algorithms. Usually the rank of the matrix is not known in advance. Error estimators and the adaptive randomized range finder makes it possible to find a very good approximation of the exact SVD decomposition. Using this method, the approximate rank of the matrix can be estimated. The accuracy of the approximation can be estimated with no additional computational cost. When singular values decay slowly, the algorithm should be modified for increased efficiency of the randomized method. If the first 10000 eigenvalues represent 95% of energy of random field with size of 106×106, using power method only the first 1000 eigenvalues can represent 95% of energy of random field. Comparing to the original algorithm, power method can decrease computational time, and increase accuracy of approximation significantly. |
