|
Success Stories
Singular Value Decomposition (SVD)Data Processing
The Challenge
Singular value decomposition (SVD) based algorithms are used by scientists
and engineers to recognize data in noisy environments, reduce data storage
requirements, and regularization for pseudoinverse calculations. SVD is a
linear algebra technique that decomposes matrices into constituent parts, a
left-hand and right-hand matrix separated by a descriptive diagonal matrix, the
singular values, as their weighting. In many applications, the singular values of
a matrix decrease quickly with increasing rank. This property allows the user
to reduce noise or compress the matrix data by eliminating the small singular
values or the higher ranks.
|
|
|
|
Application areas for the SVD include digital signal processing (DSP),
image processing, bioinformatics and physical simulation. With technology
advances, these applications increasingly work with larger datasets—and
many more of them. The computational intensity of the SVD algorithm limits
throughput when processing many matrices, and limits usefulness when
processing large matrices on a serial computational platform. When handling
many small matrices, parallel SVD computation on a cluster of processor
would be ideal—but how does one easily distribute the work? Similarly
challenging is the implementation of the SVD algorithm in MPI or coding the
application in C/C++ or Fortran with an MPI SVD library to process large data
sets in parallel.
|
Star-P Solution
With Star-P, scientists and engineers can quickly take advantage of both data and
task-parallel SVD computation. Star-P lets users develop and optimize
their applications in the familiar MATLAB®® environment, while seamlessly
computing interactively on a multiprocessor server. With the native MATLAB®
SVD compatibility, Star-P readily enables simple conversion of existing serial
MATLAB® code for parallel computation shaving precious execution and
development time.
In a recent application of Star-P, the SVD algorithm was used for image
compression. The algorithm consisted of the following three steps: 1) load the
data, 2) compress the data, and 3) decompress the data to view the results. The
compression algorithm simply retains the SVD data up to the rank specified
- in other words, keeping only matrix u and v columns one through the
compression rank, and singular values one through compression rank.
Only one change was made to the original MATLAB® code to run in data parallel: to load the data onto the server
with the command ppload. The original algorithm is shown in Figures 1 and 2, and the algorithm is simply run in serial or
parallel as shown in Figure 3. With a single image of 500x500 pixels or larger, running Star-P on an 8-processor server, the
execution time was accelerated up to 35X.
In addition to running the SVD compression/decompression algorithm in data parallel, one could very easily run many
smaller images in task parallel. An example of running the algorithm is task parallel mode is shown in Figure 4 where the
input matrix, a, contains all the images to be compressed. By taking a set of 32 images, an order of magnitude speedups were
observed when running Star-P on an 8-processor server.
|
Summary & Metrics
-
Minimal modification of MATLAB® code to take advantage of powerful parallel computing
- Orders of magnitude data parallel speed up with large images or data objects
- High-speed processing of many images using task parallel computation
| |
Back to Success Stories |
|
Star-P Support
Blog
Email
Page
