Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.

Development and Implementation of NURBS Models of Quadratic Curves and Surfaces

This article goes into the development of NURBS models of quadratic curves and surfaces. Curves and surfaces which could be represented by one general equation (one for the curves and one for the surfaces) are addressed. The research examines the curves: ellipse, parabola and hyperbola, the surfaces: ellipsoid, paraboloid, hyperboloid, double hyperboloid, hyperbolic paraboloid and cone, and the cylinders: elliptic, parabolic and hyperbolic. Many real objects which have to be modeled in 3D applications possess specific features. Because of this these geometric objects have been chosen. Using the NURBS models presented here, specialized software modules (plug-ins) have been developed for a 3D graphic system. An analysis of their implementation and the primitives they create has been performed.