SQL Server : How to make "Update Statistics" faster? We have a table with a 1 column Primary Key on and 
                      an UNIQUE Non-Clustered Index with 16 columns.

This table has more than 20695780 Rows and on every day new records inserted between 30000 and 35000.

After insertion process, we have many other processes those refer this table.

On every day, before proceeding further, after insert we do an Update Statistics with 30 Percent Sample on this table.

After this when we do rest processes then we are not facing problem and everything goes smoothly.

Now the problem is if we do Update Statistics then it is taking more than 15 Minutes.

We need a solution: -
    To make this "Update Statistics" faster OR 
    Can we perform a parallel Update Stats on this table with other processes OR 
    Instead of "Update Statistics" can we go for REBUILD INDEXES (need to know it will update all Statistics or not)? OR 
    Any other solution by which we can save this 15 minutes.

Please advice.
I would start by seeing if you have any statistics that aren't being used.  Unfortunately that isn't possible directly but you could start by looking at your indexes and seeing if any of them are worth getting rid of.  If you can eliminate some of your indexes and/or statistics that will improve your run time for the UPDATE STATISTICS.  You can find out which indexes are actually in use by looking at sys.dm_db_index_usage_stats.

Here are a couple of links I used for reference although you can do a quick google search and find dozens.


SQL SERVER – Identifying Statistics Used by Query 
SQL SERVER – 2008 – Find If Index is Being Used in Database


Also as a general suggestion if you partition your table using a "partitioned view" so you have "old data" and "new data" then you can schedule your statistcs updates separetly.  For example let's say you partition your data by year.  You run the daily UPDATE STATISTICS on just the current years partition.  If there are no updates on previous years data then you don't have to worry about statistics updates on those partitions at all.  If there are updates on previous years data you can either 


Let them update themselves using the auto update functionality or
Update them say once a week 
And/or update them during an off hour time.