1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>Solving Linear Least Squares Problems</TITLE>
<META NAME="description" CONTENT="Solving Linear Least Squares Problems">
<META NAME="keywords" CONTENT="slug">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="slug.css">
</HEAD>
<BODY LANG="EN" >
<A NAME="tex2html3685" HREF="node119.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3683" HREF="node117.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3677" HREF="node117.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3687" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html3688" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html3686" HREF="node119.html">Eigenvalue Problems</A>
<B>Up:</B> <A NAME="tex2html3684" HREF="node117.html">Solving Linear Systems of </A>
<B> Previous:</B> <A NAME="tex2html3678" HREF="node117.html">Solving Linear Systems of </A>
<BR> <P>
<H3><A NAME="SECTION04526100000000000000">Solving Linear Least Squares Problems</A></H3>
<A NAME="subsecblockqr"> </A>
<P>
Table <A HREF="node118.html#tablsperf">5.11</A><A NAME="3993"> </A>
summarizes performance results obtained for the ScaLAPACK routine
PSGELS<A NAME="3994"> </A>/PDGELS<A NAME="3995"> </A> that
solves full-rank linear least squares problems. Solving such problems
of the form <IMG WIDTH=112 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline16768" SRC="img398.gif">, where <I>x</I> and <I>b</I>
are vectors and <I>A</I> is a rectangular matrix having full rank is
traditionally achieved via the computation of the <I>QR</I> factorization
of the matrix <I>A</I>. In ScaLAPACK, the <I>QR</I> factorization
<A NAME="3997"> </A>
is based on the use of elementary Householder
<A NAME="3998"> </A>
matrices of the general form
<BR><IMG WIDTH=306 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16782" SRC="img399.gif"><BR>
where <I>v</I> is a column vector and <IMG WIDTH=9 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline14435" SRC="img234.gif"> is a scalar. This leads
to an algorithm with excellent vector performance, especially
if coded to use Level 2 PBLAS.
<P>
The key to developing a distributed block form of this algorithm
is to represent a product of <I>K</I> elementary Householder
matrices of order <I>N</I> as a block form of a Householder matrix.
<A NAME="3999"> </A>
This can be done in various ways. ScaLAPACK uses the form
[<A HREF="node189.html#schreiber87a">108</A>]
<BR><IMG WIDTH=353 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath16792" SRC="img400.gif"><BR>
where <I>V</I> is an <I>N</I>-by-<I>K</I> matrix whose columns are the
individual vectors <IMG WIDTH=99 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline16800" SRC="img401.gif"> associated with
the Householder matrices <IMG WIDTH=117 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline16802" SRC="img402.gif"> and <I>T</I>
is an upper triangular matrix of order <I>K</I>. Extra work is
required to compute the elements of <I>T</I>, but this is compensated
for by the greater speed of applying the block form.
<P><A NAME="4002"> </A><A NAME="tablsperf"> </A><IMG WIDTH=747 HEIGHT=605 ALIGN=BOTTOM ALT="table4001" SRC="img403.gif"><BR>
<STRONG>Table 5.11:</STRONG> Speed in Mflop/s of PSGELS/PDGELS for square matrices of
order <I>N</I><BR>
<P>
<P>
<BR> <HR>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
