Abstract: Randomness appears widely in practical engineering problems, and nonlinear stochastic response analysis of complex structures is one of the major difficulties. Fortunately, the probability density evolution method proposed in recent years has provided a feasible way to solve this kind of problem. Due to the complexity of practical engineering problems, however, the probability density evolution function is commonly solved by time-consuming numerical methods. Hence, it is crucial to improve the computational efficiency and accuracy of these numerical algorithms. Base on the non-uniform mesh partitioning technique, a new kind of non-uniform time step TVD (total variation diminishing) scheme for probability density evolution function was derived, which improves the computational efficiency by reducing the number of iterations to 43.4%. With the increase of sample duration, the error of estimated mean value remained almost constant, while the error of estimated standard deviation increased accordingly, but the increase rate tended to diminish. The computing time also increased as the sample duration increased, but unusual cases appeared due to the adaptive time step mesh partitioning of the randomly generated samples. In addition, a new kind of initial condition with cosine function form is proposed based on the conventional initial condition with pulse-like function form. The result revealed that the initial condition with pulse-like function form is a special case of the proposed cosine function form initial condition, and the initial condition with cosine function form possesses better accuracy than the initial condition with pulse-like function form when a proper parameter is selected. The improved TVD scheme for probability density evolution equation on non-uniform time step grids with improved initial condition is illustrated with several numerical examples provided in the last section. The work accomplished in this paper is a supplement for the solving method of probability density evolution equation, and provides a basis for engineering application.