lib/PDL/MatrixOps.pm

filter: Statementstmt 81.0% 47 / 58 Branchbran 28.1% 9 / 32 Conditioncond 16.6% 3 / 18 MC/DCmcdc 0.0% 0 / 12 Subroutinesub 71.4% 5 / 7 Podpod 0.0% 0 / 4 totaltotal 48.8% 64 / 131 CC 23 SCAR 24.5
CC
23
Cov
55%
eigens_sym
14.7
eigens_sym
14.7
eigens
10.5
CRAP 11.6
« blib/lib/PDL/IO/STL.pm ↑ Summary blib/lib/PDL/IO/Storable.pm »
1 #
2 # GENERATED WITH PDL::PP from lib/PDL/MatrixOps.pd! Don't modify!
3 #
4 package PDL::MatrixOps;
5  
6 1 our @EXPORT_OK = qw(identity gurney stretcher inv det determinant eigens_sym eigens svd lu_decomp lu_decomp2 lu_backsub simq squaretotri tritosquare tricpy tritosym mstack augment );
7 1 our %EXPORT_TAGS = (Func=>\@EXPORT_OK);
8  
9 71 ▶use PDL::Core;
Subroutine BEGIN: called CC=1 SCAR=0.0
10 71 ▶use PDL::Exporter;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 71 ▶use DynaLoader;
Subroutine BEGIN: called CC=1 SCAR=0.0
12  
13  
14
15 1 our @ISA = ( 'PDL::Exporter','DynaLoader' );
16 1 push @PDL::Core::PP, __PACKAGE__;
17 1 bootstrap PDL::MatrixOps ;
18  
19  
20  
21  
22  
23  
24  
25  
26 #line 14 "lib/PDL/MatrixOps.pd"
27  
28 =encoding utf8
29  
30 use strict;
31 use warnings;
32  
33 =head1 NAME
34  
35 PDL::MatrixOps -- Some Useful Matrix Operations
36  
37 =head1 SYNOPSIS
38  
39 $inv = $x->inv;
40  
41 $det = $x->det;
42  
43 ($lu,$perm,$par) = $x->lu_decomp;
44 $y = lu_backsub($lu,$perm,$z); # solve $x x $y = $z
45  
46 =head1 DESCRIPTION
47  
48 PDL::MatrixOps is PDL's built-in matrix manipulation code. It
49 contains utilities for many common matrix operations: inversion,
50 determinant finding, eigenvalue/vector finding, singular value
51 decomposition, etc. PDL::MatrixOps routines are written in a mixture
52 of Perl and C, so that they are reliably present even when there is no
53 external library available (e.g.
54 L<PDL::LinearAlgebra> or any of the PDL::GSL family of modules).
55  
56 Matrix manipulation, particularly with large matrices, is a
57 challenging field and no one algorithm is suitable in all cases. The
58 utilities here use general-purpose algorithms that work acceptably for
59 many cases but might not scale well to very large or pathological
60 (near-singular) matrices.
61  
62 Except as noted, the matrices are PDLs whose 0th dimension ranges over
63 column and whose 1st dimension ranges over row. The matrices appear
64 correctly when printed.
65  
66 These routines should work OK with L<PDL::Matrix> objects
67 as well as with normal PDLs.
68  
69 =head1 TIPS ON MATRIX OPERATIONS
70  
71 Like most computer languages, PDL addresses matrices in (column,row)
72 order in most cases; this corresponds to (X,Y) coordinates in the
73 matrix itself, counting rightwards and downwards from the upper left
74 corner. This means that if you print a PDL that contains a matrix,
75 the matrix appears correctly on the screen, but if you index a matrix
76 element, you use the indices in the reverse order that you would in a
77 math textbook. If you prefer your matrices indexed in (row, column)
78 order, you can try using the L<PDL::Matrix> object, which
79 includes an implicit exchange of the first two dimensions but should
80 be compatible with most of these matrix operations. TIMTOWDTI.
81  
82 Matrices, row vectors, and column vectors can be multiplied with the 'x'
83 operator (which is, of course, broadcastable):
84  
85 $m3 = $m1 x $m2;
86 $col_vec2 = $m1 x $col_vec1;
87 $row_vec2 = $row_vec1 x $m1;
88 $scalar = $row_vec x $col_vec;
89  
90 Because of the (column,row) addressing order, 1-D PDLs are treated as
91 _row_ vectors; if you want a _column_ vector you must add a dummy dimension:
92  
93 $rowvec = pdl(1,2); # row vector
94 $colvec = $rowvec->slice('*1'); # 1x2 column vector
95 $matrix = pdl([[3,4],[6,2]]); # 2x2 matrix
96 $rowvec2 = $rowvec x $matrix; # right-multiplication by matrix
97 $colvec = $matrix x $colvec; # left-multiplication by matrix
98 $m2 = $matrix x $rowvec; # Throws an error
99  
100 Implicit broadcasting works correctly with most matrix operations, but
101 you must be extra careful that you understand the dimensionality. In
102 particular, matrix multiplication and other matrix ops need nx1 PDLs
103 as row vectors and 1xn PDLs as column vectors. In most cases you must
104 explicitly include the trailing 'x1' dimension in order to get the expected
105 results when you broadcast over multiple row vectors.
106  
107 When broadcasting over matrices, it's very easy to get confused about
108 which dimension goes where. It is useful to include comments with
109 every expression, explaining what you think each dimension means:
110  
111 $x = xvals(360)*3.14159/180; # (angle)
112 $rot = cat(cat(cos($x),sin($x)), # rotmat: (col,row,angle)
113 cat(-sin($x),cos($x)));
114  
115 =head1 ACKNOWLEDGEMENTS
116  
117 MatrixOps includes algorithms and pre-existing code from several
118 origins. In particular, C<eigens_sym> is the work of Stephen Moshier,
119 C<svd> uses an SVD subroutine written by Bryant Marks, and C<eigens>
120 uses a subset of the Small Scientific Library by Kenneth Geisshirt.
121 They are free software, distributable under same terms as PDL itself.
122  
123 =head1 NOTES
124  
125 This is intended as a general-purpose linear algebra package for
126 small-to-mid sized matrices. The algorithms may not scale well to
127 large matrices (hundreds by hundreds) or to near singular matrices.
128  
129 If there is something you want that is not here, please add and
130 document it!
131  
132 =cut
133  
134 use Carp;
135 use strict;
136 #line 137 "lib/PDL/MatrixOps.pm"
137  
138  
139 =head1 FUNCTIONS
140  
141 =cut
142  
143  
144  
145  
146  
147 #line 131 "lib/PDL/MatrixOps.pd"
148  
149 =head2 identity
150  
151 =for sig
152  
153 Signature: (n; [o]a(n,n))
154  
155 =for ref
156  
157 Return an identity matrix of the specified size. If you hand in a
158 scalar, its value is the size of the identity matrix; if you hand in a
159 dimensioned PDL, the 0th dimension is the first two dimensions of the
160 matrix, with higher dimensions preserved.
161  
162 =cut
163  
164 sub identity {
165 my $n = shift;
166 my $out =
167 !(my $was_pdl = UNIVERSAL::isa($n,'PDL')) ? zeroes($n,$n) :
168 $n->getndims == 0 ? zeroes($n->type, $n->at(0),$n->at(0)) :
169 undef;
170 if (!defined $out) {
171 my @dims = $n->dims;
172 $out = zeroes($n->type, @dims[0, 0, 2..$#dims]);
173 }
174 $out->diagonal(0,1)++;
175 $was_pdl ? bless $out, ref($n) : $out;
176 }
177  
178 #line 163 "lib/PDL/MatrixOps.pd"
179  
180 =head2 gurney
181  
182 =for ref
183  
184 Turns a vector into non-square matrix. Takes two dims, one must
185 match vector dim 0.
186  
187 This is useful for dealing with a full SVD:
188  
189 =for example
190  
191 ($u,$s,$v) = svd($in, 1);
192 $reconstructed = $u x gurney($s, $in->dims) x $v->t; # same as $in
193  
194 =cut
195  
196 *gurney = \&PDL::gurney;
197 sub PDL::gurney {
198 my ($diag, $d0, $d1) = @_;
199 Carp::confess "gurney: given undef \$d0 or \$d1" if grep !defined $d0, $d1;
200 my $diag_len = $diag->dim(0);
201 Carp::confess "diagonal length $diag_len does not match either given dim $d0 or $d1" if !grep $diag_len == $_, $d0, $d1;
202 my $diff = abs($d0 - $d1);
203 my $mat = stretcher($diag);
204 return $mat if !$diff;
205 return $mat->append(zeroes($diag->type, $diff)) if $d0 > $d1;
206 $mat->t->append(zeroes($diag->type, $diff))->t;
207 }
208  
209 #line 197 "lib/PDL/MatrixOps.pd"
210  
211 =head2 stretcher
212  
213 =for sig
214  
215 Signature: (a(n); [o]b(n,n))
216  
217 =for usage
218  
219 $mat = stretcher($eigenvalues);
220  
221 =for ref
222  
223 Return a diagonal matrix with the specified diagonal elements.
224 Preserves higher dimensions.
225 As of 2.096, it will also have the same datatype.
226  
227 =cut
228  
229 sub stretcher {
230 my $in = shift;
231 my $out = zeroes($in->type, $in->dim(0), $in->dims);
232 $out->diagonal(0,1) += $in;
233 $out;
234 }
235  
236 #line 229 "lib/PDL/MatrixOps.pd"
237  
238 =head2 inv
239  
240 =for sig
241  
242 Signature: (a(m,m); sv opt )
243  
244 =for usage
245  
246 $a1 = inv($a, {$opt});
247  
248 =for ref
249  
250 Invert a square matrix.
251  
252 You feed in an NxN matrix in $a, and get back its inverse (if it
253 exists). The code is inplace-aware, so you can get back the inverse
254 in $a itself if you want -- though temporary storage is used either
255 way. You can cache the LU decomposition in an output option variable.
256  
257 C<inv> uses C<lu_decomp> by default; that is a numerically stable
258 (pivoting) LU decomposition method.
259  
260 OPTIONS:
261  
262 =over 3
263  
264 =item * s
265  
266 Boolean value indicating whether to complain if the matrix is singular. If
267 this is false, singular matrices cause inverse to barf. If it is true, then
268 singular matrices cause inverse to return undef.
269  
270 =item * lu (I/O)
271  
272 This value contains a list ref with the LU decomposition, permutation,
273 and parity values for C<$a>. If you do not mention the key, or if the
274 value is undef, then inverse calls C<lu_decomp>. If the key exists with
275 an undef value, then the output of C<lu_decomp> is stashed here (unless
276 the matrix is singular). If the value exists, then it is assumed to
277 hold the LU decomposition.
278  
279 =item * det (Output)
280  
281 If this key exists, then the determinant of C<$a> get stored here,
282 whether or not the matrix is singular.
283  
284 =back
285  
286 =cut
287  
288 *PDL::inv = \&inv;
289 sub inv {
290 my $x = shift;
291  
292 barf "inverse needs a square PDL as a matrix\n"
293 unless UNIVERSAL::isa($x,'PDL') &&
294 $x->ndims >= 2 &&
295 $x->dim(0) == $x->dim(1)
296 ;
297  
298 my $opt = shift;
299 $opt = {} unless defined($opt);
300 my $is_inplace = $x->is_inplace;
301 $x->set_inplace(0);
302  
303 my ($lu,$perm,$par);
304 if(exists($opt->{lu}) &&
305 ref $opt->{lu} eq 'ARRAY' &&
306 ref $opt->{lu}->[0] eq 'PDL') {
307 ($lu,$perm,$par) = @{$opt->{lu}};
308 } else {
309 ($lu,$perm,$par) = lu_decomp($x);
310 @{$opt->{lu}} = ($lu,$perm,$par)
311 if(ref $opt->{lu} eq 'ARRAY');
312 }
313  
314 my $det = (defined $lu) ? $lu->diagonal(0,1)->prodover * $par : pdl(0);
315 $opt->{det} = $det
316 if exists($opt->{det});
317  
318 unless($det->nelem > 1 || $det) {
319 return undef
320 if $opt->{s};
321 barf("PDL::inv: got a singular matrix or LU decomposition\n");
322 }
323  
324 my $out = lu_backsub($lu,$perm,$par,identity($x))->transpose->sever;
325 return $out if !$is_inplace;
326 $x .= $out;
327 $x;
328 }
329  
330 #line 329 "lib/PDL/MatrixOps.pd"
331  
332 =head2 det
333  
334 =for sig
335  
336 Signature: (a(m,m); sv opt)
337  
338 =for usage
339  
340 $det = det($a,{opt});
341  
342 =for ref
343  
344 Determinant of a square matrix using LU decomposition (for large matrices)
345  
346 You feed in a square matrix, you get back the determinant. Some
347 options exist that allow you to cache the LU decomposition of the
348 matrix (note that the LU decomposition is invalid if the determinant
349 is zero!). The LU decomposition is cacheable, in case you want to
350 re-use it. This method of determinant finding is more rapid than
351 recursive-descent on large matrices, and if you reuse the LU
352 decomposition it's essentially free.
353  
354 OPTIONS:
355  
356 =over 3
357  
358 =item * lu (I/O)
359  
360 Provides a cache for the LU decomposition of the matrix. If you
361 provide the key but leave the value undefined, then the LU decomposition
362 goes in here; if you put an LU decomposition here, it will be used and
363 the matrix will not be decomposed again.
364  
365 =back
366  
367 =cut
368  
369 *PDL::det = \&det;
370 sub det {
371 my ($x, $opt) = @_;
372 $opt = {} unless defined($opt);
373 my($lu,$perm,$par);
374 if(exists ($opt->{lu}) and (ref $opt->{lu} eq 'ARRAY')) {
375 ($lu,$perm,$par) = @{$opt->{lu}};
376 } else {
377 ($lu,$perm,$par) = lu_decomp($x);
378 $opt->{lu} = [$lu,$perm,$par]
379 if(exists($opt->{lu}));
380 }
381 defined $lu ? $lu->diagonal(0,1)->prodover * $par : PDL->zeroes(sbyte,1);
382 }
383  
384 #line 388 "lib/PDL/MatrixOps.pd"
385  
386 =head2 determinant
387  
388 =for sig
389  
390 Signature: (a(m,m))
391  
392 =for usage
393  
394 $det = determinant($x);
395  
396 =for ref
397  
398 Determinant of a square matrix, using recursive descent (broadcastable).
399  
400 This is the traditional, robust recursive determinant method taught in
401 most linear algebra courses. It scales like C<O(n!)> (and hence is
402 pitifully slow for large matrices) but is very robust because no
403 division is involved (hence no division-by-zero errors for singular
404 matrices). It's also broadcastable, so you can find the determinants of
405 a large collection of matrices all at once if you want.
406  
407 Matrices up to 3x3 are handled by direct multiplication; larger matrices
408 are handled by recursive descent to the 3x3 case.
409  
410 The LU-decomposition method L</det> is faster in isolation for
411 single matrices larger than about 4x4, and is much faster if you end up
412 reusing the LU decomposition of C<$a> (NOTE: check performance and
413 broadcasting benchmarks with new code).
414  
415 =cut
416  
417 *PDL::determinant = \&determinant;
418 sub determinant {
419 my($x) = shift;
420 my($n);
421 return undef unless(
422 UNIVERSAL::isa($x,'PDL') &&
423 $x->getndims >= 2 &&
424 ($n = $x->dim(0)) == $x->dim(1)
425 );
426  
427 return $x->clump(2) if($n==1);
428 if($n==2) {
429 my($y) = $x->clump(2);
430 return $y->index(0)*$y->index(3) - $y->index(1)*$y->index(2);
431 }
432 if($n==3) {
433 my($y) = $x->clump(2);
434 my $y3 = $y->index(3);
435 my $y4 = $y->index(4);
436 my $y5 = $y->index(5);
437 my $y6 = $y->index(6);
438 my $y7 = $y->index(7);
439 my $y8 = $y->index(8);
440  
441 return (
442 $y->index(0) * ( $y4 * $y8 - $y5 * $y7 )
443 + $y->index(1) * ( $y5 * $y6 - $y3 * $y8 )
444 + $y->index(2) * ( $y3 * $y7 - $y4 * $y6 )
445 );
446 }
447  
448 my($i);
449 my($sum) = zeroes($x->slice('(0),(0)'));
450  
451 # Do middle submatrices
452 for $i(1..$n-2) {
453 my $el = $x->slice("($i),(0)");
454 next if( ($el==0)->all ); # Optimize away unnecessary recursion
455 $sum += $el * (1-2*($i%2)) *
456 determinant($x->slice("0:".($i-1).",1:-1")->
457 append($x->slice(($i+1).":-1,1:-1")));
458 }
459  
460 # Do beginning and end submatrices
461 $sum += $x->slice("(0),(0)") * determinant($x->slice('1:-1,1:-1'));
462 $sum -= $x->slice("(-1),(0)") * determinant($x->slice('0:-2,1:-1')) * (1 - 2*($n % 2));
463  
464 return $sum;
465 }
466 #line 467 "lib/PDL/MatrixOps.pm"
467  
468  
469 =head2 eigens_sym
470  
471 =for sig
472  
473 Signature: ([phys]a(m); [o,phys]ev(n,n); [o,phys]e(n))
474 Types: (double)
475  
476 =for ref
477  
478 Eigenvalues and -vectors of a symmetric square matrix. If passed
479 an asymmetric matrix, the routine will warn and symmetrize it, by taking
480 the average value. That is, it will solve for 0.5*($a+$a->transpose).
481  
482 It's broadcastable, so if C<$a> is 3x3x100, it's treated as 100 separate 3x3
483 matrices, and both C<$ev> and C<$e> get extra dimensions accordingly.
484  
485 If called in scalar context it hands back only the eigenvalues. Ultimately,
486 it should switch to a faster algorithm in this case (as discarding the
487 eigenvectors is wasteful).
488  
489 The algorithm used is due to J. von Neumann, which was a rediscovery of
490 L<Jacobi's Method|http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm> .
491  
492 The eigenvectors are returned in COLUMNS of the returned PDL. That
493 makes it slightly easier to access individual eigenvectors, since the
494 0th dim of the output PDL runs across the eigenvectors and the 1st dim
495 runs across their components.
496  
497 =for example
498  
499 ($ev,$e) = eigens_sym $x; # Make eigenvector matrix
500 $vector = $ev->slice($n); # Select nth eigenvector as a column-vector
501 $vector = $ev->slice("($n)"); # Select nth eigenvector as a row-vector
502 # or to sort in descending order:
503 $indices = qsorti($ev)->slice("-1:0");
504 $sorted_ev = $ev->slice($indices); # sort values
505 $sorted_e = $e->slice(':', $indices); # sort eigenvectors
506  
507 As of 2.096, the eigenvalues are returned in ascending order.
508  
509 To compare with L<PDL::LinearAlgebra>:
510  
511 use PDL::LinearAlgebra;
512 ($val, $rvec) = msymeigen($A = pdl([3,4], [4,-3]),1,1);
513 print $val->slice(1) * $rvec->slice(1);
514 #[
515 # [ -4.472136]
516 # [ -2.236068]
517 #]
518 print $A x $rvec->slice(1);
519 #[
520 # [ -4.472136]
521 # [ -2.236068]
522 #]
523 ($rvec, $val) = eigens_sym($A); # note return values other way round
524 # otherwise the same
525  
526 =for usage
527  
528 ($ev, $e) = eigens_sym($x); # e-vects & e-values
529 $e = eigens_sym($x); # just eigenvalues
530  
531 =pod
532  
533 Broadcasts over its inputs.
534  
535 =for bad
536  
537 C<eigens_sym> ignores the bad-value flag of the input ndarrays.
538 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
539  
540 =cut
541  
542  
543  
544  
545 3 ▶sub PDL::eigens_sym {
Subroutine eigens_sym: called CC=7 SCAR=26.9
Pod undocumented
546 3 ▶ my ($x) = @_;
Subroutine eigens_sym: not called CC=7 SCAR=26.9
Pod undocumented
547 3 my @d = $x->dims;
548 3 ▶ barf "Need real square matrix for eigens_sym"
Branch: 2 branches
BranchTrueFalseTotal
if @d < 2 or $d[0] != $d[1] 0 3 3
if @d < 2 or $d[0] != $d[1] 0 0 0
Condition16%1/6
@d < 2 or $d[0] != $d[1]
l!l&&r!l&&!r
003
@d < 2 or $d[0] != $d[1]
l!l&&r!l&&!r
000
MC/DC0%0/2
@d < 2 or $d[0] != $d[1]
@d < 2 $d[0] != $d[1]
MC/DC0%0/2
@d < 2 or $d[0] != $d[1]
@d < 2 $d[0] != $d[1]
Truth table33%1/3
A or B
A= @d < 2B= $d[0] != $d[1]
ABresult
1X1
011
000
Truth table0%0/3
A or B
A= @d < 2B= $d[0] != $d[1]
ABresult
1X1
011
000
549 if @d < 2 or $d[0] != $d[1];
550 3 my ($sym) = 0.5*($x + $x->transpose);
551 3 my ($err) = PDL::max(abs($sym));
552 0 ▶ barf "Need symmetric component non-zero for eigens_sym" if $err == 0;
Branch: 2 branches
BranchTrueFalseTotal
if $err == 0 0 3 3
if $err == 0 0 0 0
553 0 $err = PDL::max(abs($x-$sym))/$err;
554 0 ▶ warn "Using symmetrized version of the matrix in eigens_sym"
Branch: 2 branches
BranchTrueFalseTotal
if $err > "1e-05" and $PDL::debug 0 3 3
if $err > "1e-05" and $PDL::debug 0 0 0
Condition16%1/6
$err > "1e-05" and $PDL::debug
!ll&&!rl&&r
300
$err > "1e-05" and $PDL::debug
!ll&&!rl&&r
000
MC/DC0%0/2
$err > "1e-05" and $PDL::debug
$err > "1e-05" $PDL::debug
MC/DC0%0/2
$err > "1e-05" and $PDL::debug
$err > "1e-05" $PDL::debug
Truth table33%1/3
A and B
A= $err > "1e-05"B= $PDL::debug
ABresult
0X0
100
111
Truth table0%0/3
A and B
A= $err > "1e-05"B= $PDL::debug
ABresult
0X0
100
111
555 if $err > 1e-5 && $PDL::debug;
556 0 PDL::_eigens_sym_int($sym->squaretotri, my $ev=PDL->null, my $e=PDL->null);
557 3 ▶ return ($ev->transpose, $e) if wantarray;
Branch: 2 branches
BranchTrueFalseTotal
if wantarray 3 0 3
if wantarray 0 0 0
558 0 $e; #just eigenvalues
559 }
560  
561  
562  
563 *eigens_sym = \&PDL::eigens_sym;
564  
565  
566  
567  
568  
569  
570 =head2 eigens
571  
572 =for sig
573  
574 Signature: ([phys]a(n,n); complex [o,phys]ev(n,n); complex [o,phys]e(n))
575 Types: (double)
576  
577 =for ref
578  
579 Complex eigenvalues and -vectors of a real square matrix.
580  
581 (See also L<"eigens_sym"|/eigens_sym>, for eigenvalues and -vectors
582 of a real, symmetric, square matrix).
583  
584 The eigens function will attempt to compute the eigenvalues and
585 eigenvectors of a square matrix with real components. If the matrix
586 is symmetric, the same underlying code as L<"eigens_sym"|/eigens_sym>
587 is used. If asymmetric, the eigenvalues and eigenvectors are computed
588 with algorithms from the sslib library. These are a slightly modified
589 version of EISPACK's C<rg> code.
590  
591 Not all square matrices are diagonalizable. If you feed in a
592 non-diagonalizable matrix, then the algorithm may fail, in which case
593 an exception will be thrown.
594  
595 C<eigens> is broadcastable, so you can solve 100 eigenproblems by
596 feeding in a 3x3x100 array. Both C<$ev> and C<$e> get extra dimensions accordingly.
597  
598 If called in scalar context C<eigens> hands back only the eigenvalues. This
599 is somewhat wasteful, as it calculates the eigenvectors anyway.
600  
601 The eigenvectors are returned in COLUMNS of the returned PDL (ie the
602 the 0 dimension). That makes it slightly easier to access individual
603 eigenvectors, since the 0th dim of the output PDL runs across the
604 eigenvectors and the 1st dim runs across their components.
605  
606 =for example
607  
608 ($ev,$e) = eigens $x; # Make eigenvector matrix
609 $vector = $ev->slice($n); # Select nth eigenvector as a column-vector
610 $vector = $ev->slice("($n)"); # Select nth eigenvector as a row-vector
611 # or to sort in descending order:
612 $indices = qsorti($ev)->slice("-1:0");
613 $sorted_ev = $ev->slice($indices); # sort values
614 $sorted_e = $e->slice(':', $indices); # sort eigenvectors
615  
616 To compare with L<PDL::LinearAlgebra>:
617  
618 use PDL::LinearAlgebra;
619 ($val, $lvec, $rvec) = meigen($A = pdl([4,-1], [2,1]),1,1);
620 print $val->slice(1) * $rvec->slice(1);
621 #[
622 # [0.894427190999916]
623 # [ 1.78885438199983]
624 #]
625 print $A x $rvec->slice(1);
626 #[
627 # [0.894427190999916]
628 # [ 1.78885438199983]
629 #]
630 ($rvec, $val) = eigens($A); # note return values other way round
631 # otherwise the same
632  
633 =for usage
634  
635 ($ev, $e) = eigens($x); # e'vects & e'vals
636 $e = eigens($x); # just eigenvalues
637  
638 =pod
639  
640 Broadcasts over its inputs.
641  
642 =for bad
643  
644 C<eigens> ignores the bad-value flag of the input ndarrays.
645 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
646  
647 =cut
648  
649  
650  
651  
652 6 ▶sub PDL::eigens {
Subroutine eigens: called CC=6 SCAR=23.5
Pod undocumented
653 6 ▶ my ($x) = @_;
Subroutine eigens: not called CC=6 SCAR=23.5
Pod undocumented
654 0 my @d = $x->dims;
655 0 ▶ barf "Need real square matrix for eigens"
Branch: 2 branches
BranchTrueFalseTotal
if @d < 2 or $d[0] != $d[1] 0 6 6
if @d < 2 or $d[0] != $d[1] 0 0 0
Condition16%1/6
@d < 2 or $d[0] != $d[1]
l!l&&r!l&&!r
006
@d < 2 or $d[0] != $d[1]
l!l&&r!l&&!r
000
MC/DC0%0/2
@d < 2 or $d[0] != $d[1]
@d < 2 $d[0] != $d[1]
MC/DC0%0/2
@d < 2 or $d[0] != $d[1]
@d < 2 $d[0] != $d[1]
Truth table33%1/3
A or B
A= @d < 2B= $d[0] != $d[1]
ABresult
1X1
011
000
Truth table0%0/3
A or B
A= @d < 2B= $d[0] != $d[1]
ABresult
1X1
011
000
656 if @d < 2 or $d[0] != $d[1];
657 0 my $deviation = PDL::max(abs($x - $x->transpose))/PDL::max(abs($x));
658 6 ▶ if ( $deviation <= 1e-5 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($deviation <= 1e-05) { } 2 4 6
if ($deviation <= 1e-05) { } 0 0 0
659 2 PDL::_eigens_sym_int($x->squaretotri, my $ev=PDL->null, my $e=PDL->null);
660 2 ▶ return $ev->transpose, $e if wantarray;
Branch: 2 branches
BranchTrueFalseTotal
if wantarray 2 0 2
if wantarray 0 0 0
661 0 return $e; #just eigenvalues
662 } else {
663 0 PDL::_eigens_int($x, my $ev=PDL->null, my $e=PDL->null);
664 3 ▶ return $ev, $e if wantarray;
Branch: 2 branches
BranchTrueFalseTotal
if wantarray 3 0 3
if wantarray 0 0 0
665 0 return $e; #just eigenvalues
666 }
667 }
668  
669  
670  
671 *eigens = \&PDL::eigens;
672  
673  
674  
675  
676  
677  
678 =head2 svd
679  
680 =for sig
681  
682 Signature: (a(n,m);
683 [o]u(nUCol=CALC($COMP(full) ? $SIZE(m) : PDLMIN($SIZE(m),$SIZE(n))),m);
684 [o]s(nSV=CALC(PDLMIN($SIZE(m),$SIZE(n))));
685 [o]v(nVCol=CALC($COMP(full) ? $SIZE(n) : PDLMIN($SIZE(m),$SIZE(n))),n);
686 [t]sbig(nSVbig=CALC($COMP(full) ? PDLMAX($SIZE(m),$SIZE(n)) : 0));
687 [t]vbig(vbigcols=CALC(
688 $COMP(full) ? PDLMAX($SIZE(n),$SIZE(m)) : 0
689 ),vbigrows=CALC(
690 PDLMAX($SIZE(n),$SIZE(m))
691 ));
692 [t]w(wcols=CALC(
693 $COMP(full) ? PDLMAX($SIZE(m),$SIZE(n)) :
694 $SIZE(m) >= $SIZE(n) ? 0 :
695 $SIZE(m)
696 ),wrows=CALC(
697 ($COMP(full) && $SIZE(m) >= $SIZE(n)) ? $SIZE(m) : $SIZE(n)
698 ));; int full)
699 Types: (double)
700  
701 =for usage
702  
703 ($u, $s, $v) = svd($a); # using default value of full=0
704 ($u, $s, $v) = svd($a, $full); # overriding default
705 svd($a, $u, $s, $v, $full); # all arguments given
706 ($u, $s, $v) = $a->svd; # method call
707 ($u, $s, $v) = $a->svd($full);
708 $a->svd($u, $s, $v, $full);
709  
710 =for ref
711  
712 Singular value decomposition of a matrix.
713  
714 Given an m x n matrix C<$a> that has m rows and n columns,
715 C<svd> computes matrices C<$u> and C<$v>, and a vector of the singular
716 values C<$s>.
717 C<svd> computes the "thin" (or "economy") SVD of C<$a>, such that C<$u> is m
718 x min(m,n), C<$v> is min(m,n) x n, and there are min(m,n) singular values.
719 As of 2.104, you do not need to transpose this yourself to ensure
720 the input is "tall" (or square).
721 The original matrix can be reconstructed as follows:
722  
723 ($u,$s,$v) = svd($x);
724 $x_copy = $u x stretcher($s) x $v->transpose;
725  
726 Also as of 2.104, you can now request the full SVD by passing
727 a true value as the C<$full> parameter. In that case, C<$u> will
728 be m x m, and C<$v> will be n x n. To reconstruct the original
729 input, use:
730  
731 ($u,$s,$v) = svd($in, 1);
732 $in_copy = $u x gurney($s, $in->dims) x $v->t; # same as $in
733  
734 If m==n, C<$u> and C<$v> can be thought of as rotation matrices that
735 convert from the original matrix's singular coordinates to final
736 coordinates, and from original coordinates to singular coordinates,
737 respectively, and C<stretcher($s)> is a diagonal scaling matrix.
738  
739 This uses J.C. Nash's implementation of a one-sided Jacobi rotation.
740 Use LAPACK (i.e. L<PDL::LinearAlgebra>) for better performance if
741 you need it.
742  
743 EXAMPLE
744  
745 The computing literature has loads of examples of how to use SVD.
746 Here's a trivial example (used in L<PDL::Transform::map|PDL::Transform/map>)
747 of how to make a matrix less, er, singular, without changing the
748 orientation of the ellipsoid of transformation:
749  
750 { my($r1,$s,$r2) = svd $x;
751 $s++; # fatten all singular values
752 $r2 *= $s; # implicit broadcasting for cheap mult.
753 $x .= $r2 x $r1; # a gets r2 x ess x r1
754 }
755  
756 =pod
757  
758 Broadcasts over its inputs.
759  
760 =for bad
761  
762 C<svd> ignores the bad-value flag of the input ndarrays.
763 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
764  
765 =cut
766  
767  
768  
769  
770 *svd = \&PDL::svd;
771  
772  
773  
774  
775  
776 #line 775 "lib/PDL/MatrixOps.pd"
777  
778 =head2 lu_decomp
779  
780 =for sig
781  
782 Signature: (a(m,m); [o]lu(m,m); [o]perm(m); [o]parity)
783  
784 =for ref
785  
786 LU decompose a matrix, with row permutation
787  
788 =for usage
789  
790 ($lu, $perm, $parity) = lu_decomp($x);
791 $lu = lu_decomp($x, $perm, $par); # $perm and $par are outputs!
792 lu_decomp($x->inplace,$perm,$par); # Everything in place.
793  
794 =for description
795  
796 C<lu_decomp> returns an LU decomposition of a square matrix,
797 using Crout's method with partial pivoting. It's ported
798 from I<Numerical Recipes>. The partial pivoting keeps it
799 numerically stable but means a little more overhead from
800 broadcasting.
801  
802 C<lu_decomp> decomposes the input matrix into matrices L and
803 U such that LU = A, L is a subdiagonal matrix, and U is a
804 superdiagonal matrix. By convention, the diagonal of L is
805 all 1's.
806  
807 The single output matrix contains all the variable elements
808 of both the L and U matrices, stacked together. Because the
809 method uses pivoting (rearranging the lower part of the
810 matrix for better numerical stability), you have to permute
811 input vectors before applying the L and U matrices. The
812 permutation is returned either in the second argument or, in
813 list context, as the second element of the list. You need
814 the permutation for the output to make any sense, so be sure
815 to get it one way or the other.
816  
817 LU decomposition is the answer to a lot of matrix questions,
818 including inversion and determinant-finding, and C<lu_decomp>
819 is used by L</inv>.
820  
821 If you pass in C<$perm> and C<$parity>, they either must be
822 predeclared PDLs of the correct size ($perm is an n-vector,
823 C<$parity> is a scalar) or scalars.
824  
825 If the matrix is singular, then the LU decomposition might
826 not be defined; in those cases, C<lu_decomp> silently returns
827 undef. Some singular matrices LU-decompose just fine, and
828 those are handled OK but give a zero determinant (and hence
829 can't be inverted).
830  
831 C<lu_decomp> uses pivoting, which rearranges the values in the
832 matrix for more numerical stability. This makes it really
833 good for large and even near-singular matrices. There is
834 a non-pivoting version C<lu_decomp2> available which is
835 from 5 to 60 percent faster for typical problems at
836 the expense of failing to compute a result in some cases.
837  
838 Now that the C<lu_decomp> is broadcasted, it is the recommended
839 LU decomposition routine. It no longer falls back to C<lu_decomp2>.
840  
841 C<lu_decomp> is ported from I<Numerical Recipes> to PDL. It
842 should probably be implemented in C.
843  
844 =cut
845  
846 *PDL::lu_decomp = \&lu_decomp;
847  
848 sub lu_decomp {
849 my($in) = shift;
850 my($permute) = shift;
851 my($parity) = shift;
852 my($sing_ok) = shift;
853  
854 my $TINY = 1e-30;
855  
856 barf("lu_decomp requires a square (2D) PDL\n")
857 if(!UNIVERSAL::isa($in,'PDL') ||
858 $in->ndims < 2 ||
859 $in->dim(0) != $in->dim(1));
860  
861 my($n) = $in->dim(0);
862 my($n1) = $n; $n1--;
863  
864 my($inplace) = $in->is_inplace;
865 my($out) = ($inplace) ? $in : $in->copy;
866  
867 if(defined $permute) {
868 barf('lu_decomp: permutation vector must match the matrix')
869 if(!UNIVERSAL::isa($permute,'PDL') ||
870 $permute->ndims != 1 ||
871 $permute->dim(0) != $out->dim(0));
872 $permute .= PDL->xvals($in->dim(0));
873 } else {
874 $permute = $in->slice("(0)")->xvals;
875 }
876  
877 if(defined $parity) {
878 barf('lu_decomp: parity must be a scalar PDL')
879 if(!UNIVERSAL::isa($parity,'PDL') ||
880 $parity->dim(0) != 1);
881 $parity .= 1.0;
882 } else {
883 $parity = $in->slice('(0),(0)')->ones;
884 }
885  
886 my($scales) = $in->copy->abs->maximum; # elementwise by rows
887  
888 if(($scales==0)->sum) {
889 return undef;
890 }
891  
892 # Some holding tanks
893 my($tmprow) = $out->slice('(0)')->zeroes;
894 $tmprow = $tmprow->double if $tmprow->type < double;
895 my($tmpval) = $tmprow->slice('(0)')->sever;
896  
897 my($col,$row);
898 for $col(0..$n1) {
899 for $row(1..$n1) {
900 my($klim) = $row<$col ? $row : $col;
901 if($klim > 0) {
902 $klim--;
903 my($el) = $out->index2d($col,$row);
904 $el -= ( $out->slice("($col),0:$klim") *
905 $out->slice("0:$klim,($row)") )->sumover;
906 }
907  
908 }
909  
910 # Figure a_ij, with pivoting
911  
912 if($col < $n1) {
913 # Find the maximum value in the rest of the row
914 my $sl = $out->slice("($col),$col:$n1");
915 my $wh = $sl->abs->maximum_ind;
916 my $big = $sl->index($wh)->sever;
917  
918 # Permute if necessary to make the diagonal the maximum
919 # if($wh != 0)
920 { # Permute rows to place maximum element on diagonal.
921 my $whc = $wh+$col;
922  
923 my $sl1 = $out->mv(1,0)->index($whc->slice("*$n"));
924 my $sl2 = $out->slice(":,($col)");
925 $tmprow .= $sl1; $sl1 .= $sl2; $sl2 .= $tmprow;
926  
927 $sl1 = $permute->index($whc);
928 $sl2 = $permute->index($col);
929 $tmpval .= $sl1; $sl1 .= $sl2; $sl2 .= $tmpval;
930  
931 $parity->where($wh>0) *= -1.0;
932 }
933  
934 # LAPACK cgetrf does not try fix singularity so nor do we, even though NR does
935 my $notbig = $big->where(abs($big) < $TINY);
936 return if !$notbig->isempty;
937  
938 # Divide by the diagonal element (which is now the largest element)
939 my $tout;
940 ($tout = $out->slice("($col),".($col+1).":$n1")) /= $big->slice('*1');
941 } # end of pivoting part
942 } # end of column loop
943  
944 wantarray ? ($out,$permute,$parity) : $out;
945 }
946  
947 #line 950 "lib/PDL/MatrixOps.pd"
948  
949 =head2 lu_decomp2
950  
951 =for sig
952  
953 Signature: (a(m,m); [o]lu(m,m))
954  
955 =for ref
956  
957 LU decompose a matrix, with no row permutation
958  
959 =for usage
960  
961 ($lu, $perm, $parity) = lu_decomp2($x);
962  
963 $lu = lu_decomp2($x,$perm,$parity); # or
964 $lu = lu_decomp2($x); # $perm and $parity are optional
965  
966 lu_decomp($x->inplace,$perm,$parity); # or
967 lu_decomp($x->inplace); # $perm and $parity are optional
968  
969 =for description
970  
971 C<lu_decomp2> works just like L</lu_decomp>, but it does B<no>
972 pivoting at all. For compatibility with L</lu_decomp>, it
973 will give you a permutation list and a parity scalar if you ask
974 for them -- but they are always trivial.
975  
976 Because C<lu_decomp2> does not pivot, it is numerically B<unstable> --
977 that means it is less precise than L</lu_decomp>, particularly for
978 large or near-singular matrices. There are also specific types of
979 non-singular matrices that confuse it (e.g. ([0,-1,0],[1,0,0],[0,0,1]),
980 which is a 90 degree rotation matrix but which confuses C<lu_decomp2>).
981  
982 On the other hand, if you want to invert rapidly a few hundred thousand
983 small matrices and don't mind missing one or two, it could be the ticket.
984 It can be up to 60% faster at the expense of possible failure of the
985 decomposition for some of the input matrices.
986  
987 The output is a single matrix that contains the LU decomposition of C<$a>;
988 you can even do it in-place, thereby destroying C<$a>, if you want. See
989 L</lu_decomp> for more information about LU decomposition.
990  
991 C<lu_decomp2> is ported from I<Numerical Recipes> into PDL.
992  
993 =cut
994  
995 *PDL::lu_decomp2 = \&lu_decomp2;
996  
997 sub lu_decomp2 {
998 my($in) = shift;
999 my($perm) = shift;
1000 my($par) = shift;
1001  
1002 my($sing_ok) = shift;
1003  
1004 my $TINY = 1e-30;
1005  
1006 barf("lu_decomp2 requires a square (2D) PDL\n")
1007 if(!UNIVERSAL::isa($in,'PDL') ||
1008 $in->ndims < 2 ||
1009 $in->dim(0) != $in->dim(1));
1010  
1011 my($n) = $in->dim(0);
1012 my($n1) = $n; $n1--;
1013  
1014 my($inplace) = $in->is_inplace;
1015 my($out) = ($inplace) ? $in : $in->copy;
1016  
1017 if(defined $perm) {
1018 barf('lu_decomp2: permutation vector must match the matrix')
1019 if(!UNIVERSAL::isa($perm,'PDL') ||
1020 $perm->ndims != 1 ||
1021 $perm->dim(0) != $out->dim(0));
1022 $perm .= PDL->xvals($in->dim(0));
1023 } else {
1024 $perm = PDL->xvals($in->dim(0));
1025 }
1026  
1027 if(defined $par) {
1028 barf('lu_decomp: parity must be a scalar PDL')
1029 if(!UNIVERSAL::isa($par,'PDL') ||
1030 $par->nelem != 1);
1031 $par .= 1.0;
1032 } else {
1033 $par = pdl(1.0);
1034 }
1035  
1036 my $diagonal = $out->diagonal(0,1);
1037  
1038 my($col,$row);
1039 for $col(0..$n1) {
1040 for $row(1..$n1) {
1041 my($klim) = $row<$col ? $row : $col;
1042 if($klim > 0) {
1043 $klim--;
1044 my($el) = $out->index2d($col,$row);
1045  
1046 $el -= ( $out->slice("($col),0:$klim") *
1047 $out->slice("0:$klim,($row)") )->sumover;
1048 }
1049  
1050 }
1051  
1052 # Figure a_ij, with no pivoting
1053 if($col < $n1) {
1054 # Divide the rest of the column by the diagonal element
1055 $out->slice("($col),".($col+1).":$n1") /= $diagonal->index($col)->dummy(0,$n1-$col);
1056 }
1057  
1058 } # end of column loop
1059  
1060 wantarray ? ($out,$perm,$par) : $out;
1061 }
1062  
1063 #line 1071 "lib/PDL/MatrixOps.pd"
1064  
1065 =head2 lu_backsub
1066  
1067 =for sig
1068  
1069 Signature: (lu(m,m); perm(m); b(m))
1070  
1071 =for ref
1072  
1073 Solve A x = B for matrix A, by back substitution into A's LU decomposition.
1074  
1075 =for usage
1076  
1077 ($lu,$perm,$par) = lu_decomp($A);
1078  
1079 $x = lu_backsub($lu,$perm,$par,$A); # or
1080 $x = lu_backsub($lu,$perm,$B); # $par is not required for lu_backsub
1081  
1082 lu_backsub($lu,$perm,$B->inplace); # modify $B in-place
1083  
1084 $x = lu_backsub(lu_decomp($A),$B); # (ignores parity value from lu_decomp)
1085  
1086 # starting from square matrix A and columns matrix B, with mathematically
1087 # correct dimensions
1088 $A = identity(4) + ones(4, 4);
1089 $A->slice('2,0') .= 0; # break symmetry to see if need transpose
1090 $B = sequence(2, 4);
1091 # all these functions take B as rows, interpret as though notional columns
1092 # mathematically confusing but can't change as back-compat and also
1093 # familiar to Fortran users, so just transpose inputs and outputs
1094  
1095 # using lu_backsub
1096 ($lu,$perm,$par) = lu_decomp($A);
1097 $x = lu_backsub($lu,$perm,$par, $B->transpose)->transpose;
1098  
1099 # using simq
1100 # remove all active dims
1101 @A_dims = $A->dims; @B_dims = $B->transpose->dims;
1102 splice @A_dims, 0, 2; splice @B_dims, 0, 1;
1103 @broadcast = PDL::Core::dims_filled(\@A_dims, \@B_dims);
1104 # simq modifies A, so need 1 copy per broadcast else non-first run has wrong A
1105 ($x) = simq($A->dupN(1,1,map +($A_dims[$_]//1)==1?$broadcast[$_]:1, 0..$#broadcast)->copy, $B->transpose, 0);
1106 $x = $x->transpose;
1107  
1108 # or with PDL::LinearAlgebra wrappers of LAPACK
1109 $x = msolve($A, $B);
1110  
1111 # or with LAPACK
1112 use PDL::LinearAlgebra::Real;
1113 getrf($lu=$A->copy, $ipiv=null, $info=null);
1114 getrs($lu, 1, $x=$B->transpose->copy, $ipiv, $info=null); # again, need transpose
1115 $x=$x->transpose;
1116  
1117 # or with GSL
1118 use PDL::GSL::LINALG;
1119 LU_decomp(my $lu=$A->copy, my $p=null, my $signum=null);
1120 # $B and $x, first dim is because GSL treats as vector, higher dims broadcast
1121 # so we transpose in and back out
1122 LU_solve($lu, $p, $B->transpose, my $x=null);
1123 $x=$x->transpose;
1124  
1125 # proof of the pudding is in the eating:
1126 print $A x $x;
1127  
1128 =for description
1129  
1130 Given the LU decomposition of a square matrix (from L</lu_decomp>),
1131 C<lu_backsub> does back substitution into the matrix to solve
1132 C<a x = b> for given vector C<b>. It is separated from the
1133 C<lu_decomp> method so that you can call the cheap C<lu_backsub>
1134 multiple times and not have to do the expensive LU decomposition
1135 more than once.
1136  
1137 C<lu_backsub> acts on single vectors and broadcasts in the usual
1138 way, which means that it treats C<$y> as the I<transpose>
1139 of the input. If you want to process a matrix, you must
1140 hand in the I<transpose> of the matrix, and then transpose
1141 the output when you get it back. that is because pdls are
1142 indexed by (col,row), and matrices are (row,column) by
1143 convention, so a 1-D pdl corresponds to a row vector, not a
1144 column vector.
1145  
1146 If C<$lu> is dense and you have more than a few points to
1147 solve for, it is probably cheaper to find C<a^-1> with
1148 L</inv>, and just multiply C<x = a^-1 b>.) in fact,
1149 L</inv> works by calling C<lu_backsub> with the identity
1150 matrix.
1151  
1152 C<lu_backsub> is ported from section 2.3 of I<Numerical Recipes>.
1153 It is written in PDL but should probably be implemented in C.
1154  
1155 =cut
1156  
1157 *PDL::lu_backsub = \&lu_backsub;
1158  
1159 sub lu_backsub {
1160 my ($lu, $perm, $y, $par);
1161 print STDERR "lu_backsub: entering debug version...\n" if $PDL::debug;
1162 if(@_==3) {
1163 ($lu, $perm, $y) = @_;
1164 } elsif(@_==4) {
1165 ($lu, $perm, $par, $y) = @_;
1166 }
1167  
1168 barf("lu_backsub: LU decomposition is undef -- probably from a singular matrix.\n")
1169 unless defined($lu);
1170  
1171 barf("Usage: \$x = lu_backsub(\$lu,\$perm,\$y); all must be PDLs\n")
1172 unless(UNIVERSAL::isa($lu,'PDL') &&
1173 UNIVERSAL::isa($perm,'PDL') &&
1174 UNIVERSAL::isa($y,'PDL'));
1175  
1176 my $n = $y->dim(0);
1177 my $n1 = $n; $n1--;
1178  
1179 # Make sure broadcasting dimensions are compatible.
1180 # There are two possible sources of broadcast dims:
1181 #
1182 # (1) over multiple LU (i.e., $lu,$perm) instances
1183 # (2) over multiple B (i.e., $y) column instances
1184 #
1185 # The full dimensions of the function call looks like
1186 #
1187 # lu_backsub( lu(m,m,X), perm(m,X), b(m,Y) )
1188 #
1189 # where X is the list of extra LU dims and Y is
1190 # the list of extra B dims. We have several possible
1191 # cases:
1192 #
1193 # (1) Check that m dims are compatible
1194 my $ludims = pdl($lu->dims);
1195 my $permdims = pdl($perm->dims);
1196 my $bdims = pdl($y->dims);
1197  
1198 print STDERR "lu_backsub: called with args: \$lu$ludims, \$perm$permdims, \$y$bdims\n" if $PDL::debug;
1199  
1200 my $m = $ludims->slice("(0)"); # this is the sig dimension
1201 unless ( ($ludims->slice(0) == $m) and ($ludims->slice(1) == $m) and
1202 ($permdims->slice(0) == $m) and ($bdims->slice(0) == $m)) {
1203 barf "lu_backsub: mismatched sig dimensions";
1204 }
1205  
1206 my $lunumthr = $ludims->dim(0)-2;
1207 my $permnumthr = $permdims->dim(0)-1;
1208 my $bnumthr = $bdims->dim(0)-1;
1209 unless ( ($lunumthr == $permnumthr) and ($ludims->slice("1:-1") == $permdims)->all ) {
1210 barf "lu_backsub: \$lu and \$perm broadcast dims not equal! \n";
1211 }
1212  
1213 # (2) If X == Y then default broadcasting is ok
1214 if ( ($bnumthr==$permnumthr) and ($bdims==$permdims)->all) {
1215 print STDERR "lu_backsub: have explicit broadcast dims, goto BROADCAST_OK\n" if $PDL::debug;
1216 goto BROADCAST_OK;
1217 }
1218  
1219 # (3) If X == (x,Y) then add x dummy to lu,perm
1220  
1221 # (4) If ndims(X) > ndims(Y) then must have #3
1222  
1223 # (5) If ndims(X) < ndims(Y) then foreach
1224 # non-trivial leading dim in X (x0,x1,..)
1225 # insert dummy (x0,x1) into lu and perm
1226  
1227 # This means that broadcasting occurs over all
1228 # leading non-trivial (not length 1) dims of
1229 # B unless all the broadcast dims are explicitly
1230 # matched to the LU dims.
1231  
1232 BROADCAST_OK:
1233  
1234 # Permute the vector and make a copy if necessary.
1235 my $out = $y->dummy(1,$y->dim(0))->index($perm->dummy(1));
1236 $out = $out->sever if !$y->is_inplace;
1237 print STDERR "lu_backsub: starting with \$out" . pdl($out->dims) . "\n" if $PDL::debug;
1238  
1239 # Make sure broadcasting over lu happens OK...
1240  
1241 if($out->ndims < $lu->ndims-1) {
1242 print STDERR "lu_backsub: adjusting dims for \$out" . pdl($out->dims) . "\n" if $PDL::debug;
1243 do {
1244 $out = $out->dummy(-1,$lu->dim($out->ndims+1));
1245 } while($out->ndims < $lu->ndims-1);
1246 }
1247  
1248 ## Do forward substitution into L
1249 my $row; my $r1;
1250  
1251 for $row(1..$n1) {
1252 $r1 = $row-1;
1253 $out->index($row) -= ($lu->slice("0:$r1,$row") *
1254 $out->slice("0:$r1")
1255 )->sumover;
1256 }
1257  
1258 ## Do backward substitution into U, and normalize by the diagonal
1259 my $ludiag = $lu->diagonal(0,1);
1260 $out->index($n1) /= $ludiag->index($n1)->dummy(0); # TODO: check broadcasting
1261  
1262 for ($row=$n1; $row>0; $row--) {
1263 $r1 = $row-1;
1264 $out->index($r1) -= ($lu->slice("$row:$n1,$r1") * # TODO: check broadcast dims
1265 $out->slice("$row:$n1")
1266 )->sumover;
1267 $out->index($r1) /= $ludiag->index($r1)->dummy(0); # TODO: check broadcast dims
1268 }
1269  
1270 if ($y->is_inplace) {
1271 $y->setdims([$out->dims]) if !PDL::all($y->shape == $out->shape); # assgn needs same shape
1272 $y .= $out;
1273 }
1274 $out;
1275 }
1276 #line 1277 "lib/PDL/MatrixOps.pm"
1277  
1278  
1279 =head2 simq
1280  
1281 =for sig
1282  
1283 Signature: ([io,phys]a(n,n); [phys]b(n); [o,phys]x(n); int [o,phys]ips(n); int flag)
1284 Types: (double)
1285  
1286 =for ref
1287  
1288 Solution of simultaneous linear equations, C<a x = b>.
1289 B<NB does not broadcast well>.
1290  
1291 =for usage
1292  
1293 # remove all active dims
1294 @A_dims = $A->dims; @B_dims = $B->transpose->dims;
1295 splice @A_dims, 0, 2; splice @B_dims, 0, 1;
1296 @broadcast = PDL::Core::dims_filled(\@A_dims, \@B_dims);
1297 # simq modifies A, so need 1 copy per broadcast else non-first run has wrong A
1298 ($x) = simq($newA = $A->dupN(1,1,map +($A_dims[$_]//1)==1?$broadcast[$_]:1, 0..$#broadcast)->copy, $B->transpose, 0);
1299 # $newA now contains modified $A for uses in further calls with flag=-1
1300 $x = $x->transpose;
1301  
1302 C<$a> is an C<n x n> matrix (i.e., a vector of length C<n*n>), stored row-wise:
1303 that is, C<a(i,j) = a[ij]>, where C<ij = i*n + j>.
1304  
1305 This corresponds to normal PDL usage. The contents of matrix a may be
1306 altered (but may be required for subsequent calls with flag = -1).
1307  
1308 C<$y>, C<$x>, C<$ips> are vectors of length C<n>.
1309  
1310 Set C<flag=0> to solve.
1311 Set C<flag=-1> to do a new back substitution for
1312 different C<$y> vector using the same a matrix previously reduced when
1313 C<flag=0> (the C<$ips> vector generated in the previous solution is also
1314 required).
1315  
1316 For this function to work well with broadcasting, it will need the LU
1317 decomposition part split out, so that for solving C<A x = B> only C<x>
1318 would be written to.
1319  
1320 See also L</lu_backsub>, which does the same thing with a slightly
1321 less opaque interface.
1322  
1323 =pod
1324  
1325 Broadcasts over its inputs.
1326  
1327 =for bad
1328  
1329 C<simq> ignores the bad-value flag of the input ndarrays.
1330 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1331  
1332 =cut
1333  
1334  
1335  
1336  
1337 *simq = \&PDL::simq;
1338  
1339  
1340  
1341  
1342  
1343  
1344 =head2 squaretotri
1345  
1346 =for sig
1347  
1348 Signature: (a(n,n); [o]b(m=CALC(($SIZE(n) * ($SIZE(n)+1))/2)))
1349 Types: (sbyte byte short ushort long ulong indx ulonglong longlong
1350 float double ldouble cfloat cdouble cldouble)
1351  
1352 =for usage
1353  
1354 $b = squaretotri($a);
1355 squaretotri($a, $b); # all arguments given
1356 $b = $a->squaretotri; # method call
1357 $a->squaretotri($b);
1358  
1359 =for ref
1360  
1361 Convert a lower-triangular square matrix to triangular vector storage.
1362 Ignores upper half of input.
1363  
1364 =pod
1365  
1366 Broadcasts over its inputs.
1367  
1368 =for bad
1369  
1370 C<squaretotri> does not process bad values.
1371 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1372  
1373 =cut
1374  
1375  
1376  
1377  
1378 *squaretotri = \&PDL::squaretotri;
1379  
1380  
1381  
1382  
1383  
1384  
1385 =head2 tritosquare
1386  
1387 =for sig
1388  
1389 Signature: (a(m); [o]b(n,n))
1390 Types: (sbyte byte short ushort long ulong indx ulonglong longlong
1391 float double ldouble cfloat cdouble cldouble)
1392  
1393 =for usage
1394  
1395 $b = tritosquare($a);
1396 tritosquare($a, $b); # all arguments given
1397 $b = $a->tritosquare; # method call
1398 $a->tritosquare($b);
1399  
1400 =for ref
1401  
1402 Convert a triangular vector to lower-triangular square matrix storage.
1403 Does not touch upper half of output.
1404  
1405 See also L</tritosym>, L</tricpy>.
1406  
1407 =pod
1408  
1409 Broadcasts over its inputs.
1410  
1411 =for bad
1412  
1413 C<tritosquare> does not process bad values.
1414 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1415  
1416 =cut
1417  
1418  
1419  
1420  
1421 *tritosquare = \&PDL::tritosquare;
1422  
1423  
1424  
1425  
1426  
1427  
1428 =head2 tricpy
1429  
1430 =for sig
1431  
1432 Signature: (A(m,n);[o] C(m,n); int uplo)
1433 Types: (sbyte byte short ushort long ulong indx ulonglong longlong
1434 float double ldouble cfloat cdouble cldouble)
1435  
1436 =for usage
1437  
1438 $C = tricpy($A); # using default of uplo=0
1439 $C = tricpy($A, $uplo);
1440 tricpy($A, $uplo, $C); # all arguments given
1441 $C = $A->tricpy; # method call
1442 $C = $A->tricpy($uplo);
1443 $A->tricpy($uplo, $C);
1444  
1445 =for ref
1446  
1447 Copy triangular part to another matrix.
1448  
1449 C<uplo> meanings to copy: -1 strict upper triangular, 0 = upper, 1
1450 lower, 2 strict lower. The "strict" modes are as of 2.104.
1451  
1452 Originally by Grégory Vanuxem.
1453 See also L</tritosym>, L</tritosquare>.
1454  
1455 =pod
1456  
1457 Broadcasts over its inputs.
1458  
1459 =for bad
1460  
1461 C<tricpy> does not process bad values.
1462 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1463  
1464 =cut
1465  
1466  
1467  
1468  
1469 *tricpy = \&PDL::tricpy;
1470  
1471  
1472  
1473  
1474  
1475 #line 1423 "lib/PDL/MatrixOps.pd"
1476  
1477 =head2 tritosym
1478  
1479 =for ref
1480  
1481 Returns symmetric or Hermitian matrix from lower or upper triangular matrix.
1482 Supports inplace and broadcasting.
1483  
1484 =for usage
1485  
1486 PDL = tritosym(PDL, SCALAR(uplo), SCALAR(conj))
1487 uplo : UPPER = 0 | LOWER = 1, default = 0
1488 conj : Hermitian = 1 | Symmetric = 0, default = 0;
1489  
1490 Originally by Grégory Vanuxem. Added to PDL in 2.104.
1491 See also L</tricpy>, L</tritosquare>.
1492  
1493 =cut
1494  
1495 *tritosym = \&PDL::tritosym;
1496 sub PDL::tritosym {
1497 my @dims = $_[0]->dims;
1498 barf "Require square array but got (@dims)" unless @dims >= 2 && $dims[0] == $dims[1];
1499 my ($m, $upper, $conj) = @_;
1500 $conj = 0 if $m->type->real;
1501 my $b = $m->new_or_inplace;
1502 ($conj ? $m->conj : $m)->tricpy($upper ? 2 : -1, $b->t); # strict
1503 $b->diagonal(0,1)->im .= 0 if $conj;
1504 $b;
1505 }
1506 #line 1507 "lib/PDL/MatrixOps.pm"
1507  
1508  
1509 =head2 mstack
1510  
1511 =for sig
1512  
1513 Signature: (x(n,m);y(n,p);[o]out(n,q=CALC($SIZE(m)+$SIZE(p))))
1514 Types: (sbyte byte short ushort long ulong indx ulonglong longlong
1515 float double ldouble cfloat cdouble cldouble)
1516  
1517 =for usage
1518  
1519 $out = mstack($x, $y);
1520 mstack($x, $y, $out); # all arguments given
1521 $out = $x->mstack($y); # method call
1522 $x->mstack($y, $out);
1523 $x->mstack($y) .= $data; # usable as lvalue
1524  
1525 =for ref
1526  
1527 Combine two 2D ndarrays into a single ndarray, along the second
1528 ("vertical") dim.
1529  
1530 Originally by Grégory Vanuxem.
1531  
1532 =pod
1533  
1534 Broadcasts over its inputs.
1535 Creates data-flow back and forth by default.
1536  
1537 =for bad
1538  
1539 C<mstack> does not process bad values.
1540 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1541  
1542 =cut
1543  
1544  
1545  
1546  
1547 *mstack = \&PDL::mstack;
1548  
1549  
1550  
1551  
1552  
1553  
1554 =head2 augment
1555  
1556 =for sig
1557  
1558 Signature: (x(n); y(p);[o]out(q=CALC($SIZE(n)+$SIZE(p))))
1559 Types: (sbyte byte short ushort long ulong indx ulonglong longlong
1560 float double ldouble cfloat cdouble cldouble)
1561  
1562 =for usage
1563  
1564 $out = augment($x, $y);
1565 augment($x, $y, $out); # all arguments given
1566 $out = $x->augment($y); # method call
1567 $x->augment($y, $out);
1568 $x->augment($y) .= $data; # usable as lvalue
1569  
1570 =for ref
1571  
1572 Combine two ndarrays into a single ndarray along the 0-th ("horizontal") dim.
1573  
1574 Originally by Grégory Vanuxem.
1575  
1576 =pod
1577  
1578 Broadcasts over its inputs.
1579 Creates data-flow back and forth by default.
1580  
1581 =for bad
1582  
1583 C<augment> does not process bad values.
1584 It will set the bad-value flag of all output ndarrays if the flag is set for any of the input ndarrays.
1585  
1586 =cut
1587  
1588  
1589  
1590  
1591 *augment = \&PDL::augment;
1592  
1593  
1594  
1595  
1596  
1597  
1598  
1599 #line 1496 "lib/PDL/MatrixOps.pd"
1600  
1601 =head1 AUTHOR
1602  
1603 Copyright (C) 2002 Craig DeForest (deforest@boulder.swri.edu),
1604 R.J.R. Williams (rjrw@ast.leeds.ac.uk), Karl Glazebrook
1605 (kgb@aaoepp.aao.gov.au). There is no warranty. You are allowed to
1606 redistribute and/or modify this work under the same conditions as PDL
1607 itself. If this file is separated from the PDL distribution, then the
1608 PDL copyright notice should be included in this file.
1609  
1610 =cut
1611 #line 1612 "lib/PDL/MatrixOps.pm"
1612  
1613 # Exit with OK status
1614  
1615 1;
« blib/lib/PDL/IO/STL.pm ↑ Summary blib/lib/PDL/IO/Storable.pm »