| 1 | package Sidef::Types::Array::Matrix; | ||
| 2 | |||
| 3 | use utf8; | ||
| 4 | use 5.016; | ||
| 5 | use List::Util qw(); | ||
| 6 | |||
| 7 | use parent qw( | ||
| 8 | Sidef::Types::Array::Array | ||
| 9 | ); | ||
| 10 | |||
| 11 | use overload q{""} => \&_dump; | ||
| 12 | |||
| 13 | sub _is_matrix { | ||
| 14 | my ($self) = @_; | ||
| 15 | |||
| 16 | my $ref = ref($self); | ||
| 17 | |||
| 18 | if ($ref eq __PACKAGE__) { | ||
| 19 | return 1; | ||
| 20 | } | ||
| 21 | |||
| 22 | if ($ref and UNIVERSAL::isa($self, 'Sidef::Types::Array::Array')) { | ||
| 23 | |||
| 24 | foreach my $row (@$self) { # each row must an array-like object | ||
| 25 | ref($row) and UNIVERSAL::isa($row, 'Sidef::Types::Array::Array') | ||
| 26 | or return 0; | ||
| 27 | } | ||
| 28 | |||
| 29 | return 1; | ||
| 30 | } | ||
| 31 | |||
| 32 | return 0; | ||
| 33 | } | ||
| 34 | |||
| 35 | sub new { | ||
| 36 | my (undef, @rows) = @_; | ||
| 37 | bless [map { bless [@$_], 'Sidef::Types::Array::Array' } @rows]; | ||
| 38 | } | ||
| 39 | |||
| 40 | *call = \&new; | ||
| 41 | |||
| 42 | sub is_square { | ||
| 43 | my ($self) = @_; | ||
| 44 | |||
| 45 | my $rows = $#{$self}; | ||
| 46 | $rows < 0 and return Sidef::Types::Bool::Bool::TRUE; | ||
| 47 | |||
| 48 | ($rows == $#{$self->[0]}) | ||
| 49 | ? Sidef::Types::Bool::Bool::TRUE | ||
| 50 | : Sidef::Types::Bool::Bool::FALSE; | ||
| 51 | } | ||
| 52 | |||
| 53 | sub size { | ||
| 54 | my ($self) = @_; | ||
| 55 | my $rows = $#{$self}; | ||
| 56 | $rows < 0 and return ((Sidef::Types::Number::Number::ZERO) x 2); | ||
| 57 | (Sidef::Types::Number::Number::_set_int($rows + 1), Sidef::Types::Number::Number::_set_int($#{$self->[0]} + 1)); | ||
| 58 | } | ||
| 59 | |||
| 60 | sub build { | ||
| 61 | my (undef, $n, $m, $block) = @_; | ||
| 62 | |||
| 63 | $n = CORE::int($n); | ||
| 64 | |||
| 65 | if (ref($m) eq 'Sidef::Types::Block::Block') { | ||
| 66 | ($m, $block) = ($n, $m); | ||
| 67 | } | ||
| 68 | else { | ||
| 69 | $m = CORE::int($m); | ||
| 70 | } | ||
| 71 | |||
| 72 | #<<< | ||
| 73 | bless [ | ||
| 74 | map { | ||
| 75 | my $i = Sidef::Types::Number::Number::_set_int($_); | ||
| 76 | bless([map { | ||
| 77 | $block->run( | ||
| 78 | $i, Sidef::Types::Number::Number::_set_int($_) | ||
| 79 | ); | ||
| 80 | } 0 .. $m-1], 'Sidef::Types::Array::Array') | ||
| 81 | } 0 .. $n-1 | ||
| 82 | ]; | ||
| 83 | #>>> | ||
| 84 | } | ||
| 85 | |||
| 86 | sub identity { | ||
| 87 | my (undef, $n) = @_; | ||
| 88 | |||
| 89 | $n = CORE::int($n); | ||
| 90 | |||
| 91 | bless [ | ||
| 92 | map { | ||
| 93 | bless([(Sidef::Types::Number::Number::ZERO) x ($_ - 1), Sidef::Types::Number::Number::ONE, (Sidef::Types::Number::Number::ZERO) x ($n - $_)], | ||
| 94 | 'Sidef::Types::Array::Array') | ||
| 95 | } 1 .. $n | ||
| 96 | ]; | ||
| 97 | } | ||
| 98 | |||
| 99 | *I = \&identity; | ||
| 100 | |||
| 101 | sub column { | ||
| 102 | my ($self, $n) = @_; | ||
| 103 | $n = CORE::int($n); | ||
| 104 | bless [map { $_->[$n] } @$self], 'Sidef::Types::Array::Array'; | ||
| 105 | } | ||
| 106 | |||
| 107 | *col = \&column; | ||
| 108 | *get_column = \&column; | ||
| 109 | |||
| 110 | sub row { | ||
| 111 | my ($self, $n) = @_; | ||
| 112 | $n = CORE::int($n); | ||
| 113 | bless [@{$self->[$n]}], 'Sidef::Types::Array::Array'; | ||
| 114 | } | ||
| 115 | |||
| 116 | *get_row = \&row; | ||
| 117 | |||
| 118 | sub zero { | ||
| 119 | my (undef, $n, $m) = @_; | ||
| 120 | |||
| 121 | $n = CORE::int($n); | ||
| 122 | $m = defined($m) ? CORE::int($m) : $n; | ||
| 123 | |||
| 124 | #<<< | ||
| 125 | bless [ | ||
| 126 | map { | ||
| 127 | bless([(Sidef::Types::Number::Number::ZERO) x $m], 'Sidef::Types::Array::Array') | ||
| 128 | } 1 .. $n | ||
| 129 | ]; | ||
| 130 | #>>> | ||
| 131 | } | ||
| 132 | |||
| 133 | sub rand { | ||
| 134 | my (undef, $n, $m) = @_; | ||
| 135 | |||
| 136 | $n = CORE::int($n); | ||
| 137 | $m = defined($m) ? CORE::int($m) : $n; | ||
| 138 | |||
| 139 | #<<< | ||
| 140 | bless [ | ||
| 141 | map { | ||
| 142 | bless([map { | ||
| 143 | (Sidef::Types::Number::Number::ONE)->rand | ||
| 144 | } 1 .. $m], 'Sidef::Types::Array::Array') | ||
| 145 | } 1 .. $n | ||
| 146 | ]; | ||
| 147 | #>>> | ||
| 148 | } | ||
| 149 | |||
| 150 | sub scalar { | ||
| 151 | my (undef, $n, $value) = @_; | ||
| 152 | |||
| 153 | $n = CORE::int($n); | ||
| 154 | |||
| 155 | bless [ | ||
| 156 | map { bless([(Sidef::Types::Number::Number::ZERO) x ($_ - 1), $value, (Sidef::Types::Number::Number::ZERO) x ($n - $_)], 'Sidef::Types::Array::Array') } | ||
| 157 | 1 .. $n | ||
| 158 | ]; | ||
| 159 | } | ||
| 160 | |||
| 161 | sub row_vector { | ||
| 162 | my (undef, @list) = @_; | ||
| 163 | bless [bless(\@list, 'Sidef::Types::Array::Array')]; | ||
| 164 | } | ||
| 165 | |||
| 166 | sub column_vector { | ||
| 167 | my (undef, @list) = @_; | ||
| 168 | bless [map { bless([$_], 'Sidef::Types::Array::Array') } @list]; | ||
| 169 | } | ||
| 170 | |||
| 171 | *col_vector = \&column_vector; | ||
| 172 | |||
| 173 | sub _new_diagonal { | ||
| 174 | my (undef, @diag) = @_; | ||
| 175 | my $n = scalar(@diag); | ||
| 176 | #<<< | ||
| 177 | __PACKAGE__->new([ | ||
| 178 | map { [ | ||
| 179 | (Sidef::Types::Number::Number::ZERO) x ($_ - 1), | ||
| 180 | shift(@diag), | ||
| 181 | (Sidef::Types::Number::Number::ZERO) x ($n - $_) | ||
| 182 | ] } 1 .. $n | ||
| 183 | ]); | ||
| 184 | #>>> | ||
| 185 | } | ||
| 186 | |||
| 187 | sub _new_anti_diagonal { | ||
| 188 | my (undef, @diag) = @_; | ||
| 189 | my $n = scalar(@diag); | ||
| 190 | #<<< | ||
| 191 | __PACKAGE__->new([ | ||
| 192 | map { [ | ||
| 193 | (Sidef::Types::Number::Number::ZERO) x ($n - $_), | ||
| 194 | shift(@diag), | ||
| 195 | (Sidef::Types::Number::Number::ZERO) x ($_ - 1) | ||
| 196 | ] } 1 .. $n | ||
| 197 | ]); | ||
| 198 | #>>> | ||
| 199 | } | ||
| 200 | |||
| 201 | sub diagonal { | ||
| 202 | my ($self) = @_; | ||
| 203 | ref($self) || goto &_new_diagonal; | ||
| 204 | bless [map { $self->[$_][$_] } 0 .. $#{$self}], 'Sidef::Types::Array::Array'; | ||
| 205 | } | ||
| 206 | |||
| 207 | sub anti_diagonal { | ||
| 208 | my ($self) = @_; | ||
| 209 | ref($self) || goto &_new_anti_diagonal; | ||
| 210 | bless [map { my $row = $self->[$_]; $row->[$#{$row} - $_] } 0 .. $#{$self}], 'Sidef::Types::Array::Array'; | ||
| 211 | } | ||
| 212 | |||
| 213 | sub rows { | ||
| 214 | my ($self, @rows) = @_; | ||
| 215 | ref($self) && return $self->to_a; | ||
| 216 | bless [map { bless([@$_], 'Sidef::Types::Array::Array') } @rows]; | ||
| 217 | } | ||
| 218 | |||
| 219 | *from_rows = \&rows; | ||
| 220 | |||
| 221 | sub columns { | ||
| 222 | my ($self, @cols) = @_; | ||
| 223 | |||
| 224 | ref($self) && return $self->transpose->to_a; | ||
| 225 | |||
| 226 | my $max = List::Util::max(map { scalar(@$_) } @cols); | ||
| 227 | |||
| 228 | bless [ | ||
| 229 | map { | ||
| 230 | my $i = $_; | ||
| 231 | bless [map { $_->[$i] } @cols], 'Sidef::Types::Array::Array' | ||
| 232 | } 0 .. $max - 1 | ||
| 233 | ]; | ||
| 234 | } | ||
| 235 | |||
| 236 | *cols = \&columns; | ||
| 237 | *from_cols = \&columns; | ||
| 238 | *from_columns = \&columns; | ||
| 239 | |||
| 240 | sub vector_rows { | ||
| 241 | my ($self) = @_; | ||
| 242 | bless([map { Sidef::Types::Array::Vector->new(@$_) } @$self], 'Sidef::Types::Array::Array'); | ||
| 243 | } | ||
| 244 | |||
| 245 | *vec_rows = \&vector_rows; | ||
| 246 | |||
| 247 | sub vector_columns { | ||
| 248 | my ($self) = @_; | ||
| 249 | $self->transpose->vector_rows; | ||
| 250 | } | ||
| 251 | |||
| 252 | *vec_cols = \&vector_columns; | ||
| 253 | *vec_columns = \&vector_columns; | ||
| 254 | |||
| 255 | sub each_row { | ||
| 256 | my ($self, $block) = @_; | ||
| 257 | foreach my $row (@$self) { | ||
| 258 | $block->run(Sidef::Types::Array::Vector->new(@$row)); | ||
| 259 | } | ||
| 260 | $self; | ||
| 261 | } | ||
| 262 | |||
| 263 | sub each_column { | ||
| 264 | my ($self, $block) = @_; | ||
| 265 | foreach my $col (@{$self->vector_columns}) { | ||
| 266 | $block->run($col); | ||
| 267 | } | ||
| 268 | $self; | ||
| 269 | } | ||
| 270 | |||
| 271 | sub neg { | ||
| 272 | my ($m1) = @_; | ||
| 273 | bless($m1->scalar_operator('neg')); | ||
| 274 | } | ||
| 275 | |||
| 276 | sub abs { | ||
| 277 | my ($m1) = @_; | ||
| 278 | bless($m1->scalar_operator('abs')); | ||
| 279 | } | ||
| 280 | |||
| 281 | sub add { | ||
| 282 | my ($m1, $m2) = @_; | ||
| 283 | |||
| 284 | if (ref($m2) eq 'Sidef::Types::Array::Vector') { | ||
| 285 | my @result; | ||
| 286 | foreach my $row (@$m1) { | ||
| 287 | my @new_row; | ||
| 288 | $new_row[$_] = $row->[$_]->add($m2->[$_]) for 0 .. $#$row; | ||
| 289 | push @result, bless(\@new_row, 'Sidef::Types::Array::Array'); | ||
| 290 | } | ||
| 291 | return bless \@result; | ||
| 292 | } | ||
| 293 | |||
| 294 | if (_is_matrix($m2)) { | ||
| 295 | return bless($m1->wise_operator('+', $m2)); | ||
| 296 | } | ||
| 297 | bless($m1->scalar_operator('+', $m2)); | ||
| 298 | } | ||
| 299 | |||
| 300 | sub sub { | ||
| 301 | my ($m1, $m2) = @_; | ||
| 302 | |||
| 303 | if (ref($m2) eq 'Sidef::Types::Array::Vector') { | ||
| 304 | my @result; | ||
| 305 | foreach my $row (@$m1) { | ||
| 306 | my @new_row; | ||
| 307 | $new_row[$_] = $row->[$_]->sub($m2->[$_]) for 0 .. $#$row; | ||
| 308 | push @result, bless(\@new_row, 'Sidef::Types::Array::Array'); | ||
| 309 | } | ||
| 310 | return bless \@result; | ||
| 311 | } | ||
| 312 | |||
| 313 | if (_is_matrix($m2)) { | ||
| 314 | return bless($m1->wise_operator('-', $m2)); | ||
| 315 | } | ||
| 316 | bless($m1->scalar_operator('-', $m2)); | ||
| 317 | } | ||
| 318 | |||
| 319 | sub div { | ||
| 320 | my ($m1, $m2) = @_; | ||
| 321 | |||
| 322 | if (ref($m2) eq 'Sidef::Types::Array::Vector') { | ||
| 323 | my @result; | ||
| 324 | foreach my $row (@$m1) { | ||
| 325 | my @new_row; | ||
| 326 | $new_row[$_] = $row->[$_]->div($m2->[$_]) for 0 .. $#$row; | ||
| 327 | push @result, bless(\@new_row, 'Sidef::Types::Array::Array'); | ||
| 328 | } | ||
| 329 | return bless \@result; | ||
| 330 | } | ||
| 331 | |||
| 332 | if (_is_matrix($m2)) { | ||
| 333 | return $m1->mul($m2->inv); | ||
| 334 | } | ||
| 335 | bless($m1->scalar_operator('/', $m2)); | ||
| 336 | } | ||
| 337 | |||
| 338 | sub mul { | ||
| 339 | my ($m1, $m2) = @_; | ||
| 340 | |||
| 341 | if (ref($m2) eq 'Sidef::Types::Array::Vector') { | ||
| 342 | my @result; | ||
| 343 | foreach my $row (@$m1) { | ||
| 344 | my $sum = Sidef::Types::Number::Number::ZERO; | ||
| 345 | $sum = $sum->add($row->[$_]->mul($m2->[$_])) for 0 .. $#$row; | ||
| 346 | push @result, $sum; | ||
| 347 | } | ||
| 348 | return bless(\@result, 'Sidef::Types::Array::Vector'); | ||
| 349 | } | ||
| 350 | |||
| 351 | if (!_is_matrix($m2)) { | ||
| 352 | return bless($m1->scalar_operator('*', $m2)); | ||
| 353 | } | ||
| 354 | |||
| 355 | my @a = map { [@$_] } @$m1; | ||
| 356 | my @b = map { [@$_] } @$m2; | ||
| 357 | |||
| 358 | my @c; | ||
| 359 | |||
| 360 | my $a_rows = $#a; | ||
| 361 | my $b_rows = $#b; | ||
| 362 | my $b_cols = $#{$b[0]}; | ||
| 363 | |||
| 364 | foreach my $i (0 .. $a_rows) { | ||
| 365 | foreach my $j (0 .. $b_cols) { | ||
| 366 | foreach my $k (0 .. $b_rows) { | ||
| 367 | |||
| 368 | my $t = $a[$i][$k]->mul($b[$k][$j]); | ||
| 369 | |||
| 370 | if (!defined($c[$i][$j])) { | ||
| 371 | $c[$i][$j] = $t; | ||
| 372 | } | ||
| 373 | else { | ||
| 374 | $c[$i][$j] = $c[$i][$j]->add($t); | ||
| 375 | } | ||
| 376 | } | ||
| 377 | } | ||
| 378 | } | ||
| 379 | |||
| 380 | bless($_, 'Sidef::Types::Array::Array') for @c; | ||
| 381 | bless \@c; | ||
| 382 | } | ||
| 383 | |||
| 384 | sub floor { | ||
| 385 | my ($self) = @_; | ||
| 386 | bless($self->scalar_operator('floor')); | ||
| 387 | } | ||
| 388 | |||
| 389 | sub ceil { | ||
| 390 | my ($self) = @_; | ||
| 391 | bless($self->scalar_operator('ceil')); | ||
| 392 | } | ||
| 393 | |||
| 394 | sub mod { | ||
| 395 | my ($m1, $m2) = @_; | ||
| 396 | |||
| 397 | if (_is_matrix($m2)) { | ||
| 398 | return $m1->sub($m2->mul($m1->div($m2)->floor)); | ||
| 399 | } | ||
| 400 | |||
| 401 | bless($m1->scalar_operator('%', $m2)); | ||
| 402 | } | ||
| 403 | |||
| 404 | sub and { | ||
| 405 | my ($m1, $m2) = @_; | ||
| 406 | |||
| 407 | if (_is_matrix($m2)) { | ||
| 408 | return bless($m1->wise_operator('&', $m2)); | ||
| 409 | } | ||
| 410 | |||
| 411 | bless($m1->scalar_operator('&', $m2)); | ||
| 412 | } | ||
| 413 | |||
| 414 | sub or { | ||
| 415 | my ($m1, $m2) = @_; | ||
| 416 | |||
| 417 | if (_is_matrix($m2)) { | ||
| 418 | return bless($m1->wise_operator('|', $m2)); | ||
| 419 | } | ||
| 420 | |||
| 421 | bless($m1->scalar_operator('|', $m2)); | ||
| 422 | } | ||
| 423 | |||
| 424 | sub xor { | ||
| 425 | my ($m1, $m2) = @_; | ||
| 426 | |||
| 427 | if (_is_matrix($m2)) { | ||
| 428 | return bless($m1->wise_operator('^', $m2)); | ||
| 429 | } | ||
| 430 | |||
| 431 | bless($m1->scalar_operator('^', $m2)); | ||
| 432 | } | ||
| 433 | |||
| 434 | sub sum { | ||
| 435 | my ($A, $block) = @_; | ||
| 436 | Sidef::Types::Array::Array->new([map { @$_ } @$A])->sum($block); | ||
| 437 | } | ||
| 438 | |||
| 439 | *sum_by = \∑ | ||
| 440 | |||
| 441 | sub prod { | ||
| 442 | my ($A, $block) = @_; | ||
| 443 | Sidef::Types::Array::Array->new([map { @$_ } @$A])->prod($block); | ||
| 444 | } | ||
| 445 | |||
| 446 | *prod_by = \∏ | ||
| 447 | |||
| 448 | sub pow { | ||
| 449 | my ($A, $pow) = @_; | ||
| 450 | |||
| 451 | my $neg = $pow->is_neg; | ||
| 452 | |||
| 453 | if ($neg) { | ||
| 454 | return $A->inv if $pow->is_mone; | ||
| 455 | $pow = $pow->abs; | ||
| 456 | } | ||
| 457 | |||
| 458 | #<<< | ||
| 459 | my $n = $#$A; | ||
| 460 | my $B = bless [map { | ||
| 461 | my $i = $_; | ||
| 462 | (bless [map { | ||
| 463 | $i == $_ | ||
| 464 | ? Sidef::Types::Number::Number::ONE | ||
| 465 | : Sidef::Types::Number::Number::ZERO | ||
| 466 | } 0 .. $n], 'Sidef::Types::Array::Array') | ||
| 467 | } 0 .. $n]; | ||
| 468 | #>>> | ||
| 469 | |||
| 470 | return $B if $pow->is_zero; | ||
| 471 | |||
| 472 | while (1) { | ||
| 473 | $B = $B->mul($A) if $pow->is_odd; | ||
| 474 | $pow = $pow->rsft(Sidef::Types::Number::Number::ONE); | ||
| 475 | last if $pow->is_zero; | ||
| 476 | $A = $A->mul($A); | ||
| 477 | } | ||
| 478 | |||
| 479 | $neg ? $B->inv : $B; | ||
| 480 | } | ||
| 481 | |||
| 482 | sub powmod { | ||
| 483 | my ($A, $pow, $mod) = @_; | ||
| 484 | |||
| 485 | if ($pow->is_neg) { | ||
| 486 | $A = $A->invmod($mod); | ||
| 487 | $pow = $pow->abs; | ||
| 488 | } | ||
| 489 | |||
| 490 | my $B = __PACKAGE__->identity($#{$A} + 1); | ||
| 491 | |||
| 492 | return $B->mod($mod) if $pow->is_zero; | ||
| 493 | |||
| 494 | while (1) { | ||
| 495 | $B = $B->mul($A)->mod($mod) if $pow->is_odd; | ||
| 496 | $pow = $pow->rsft(Sidef::Types::Number::Number::ONE); | ||
| 497 | last if $pow->is_zero; | ||
| 498 | $A = $A->mul($A)->mod($mod); | ||
| 499 | } | ||
| 500 | |||
| 501 | $B->mod($mod); | ||
| 502 | } | ||
| 503 | |||
| 504 | # Code translated from Wikipedia (+ minor tweaks): | ||
| 505 | # https://en.wikipedia.org/wiki/LU_decomposition#C_code_examples | ||
| 506 | |||
| 507 | sub _LUP_decompose { | ||
| 508 | my ($self) = @_; | ||
| 509 | |||
| 510 | my @A = map { [@$_] } @$self; | ||
| 511 | my $N = $#A; | ||
| 512 | my @P = (0 .. $N + 1); | ||
| 513 | |||
| 514 | foreach my $i (0 .. $N) { | ||
| 515 | |||
| 516 | my $maxA = Sidef::Types::Number::Number::ZERO; | ||
| 517 | my $imax = $i; | ||
| 518 | |||
| 519 | foreach my $k ($i .. $N) { | ||
| 520 | my $absA = ($A[$k][$i] // return ($N, \@A, \@P))->abs; | ||
| 521 | |||
| 522 | if ($absA->gt($maxA)) { | ||
| 523 | $maxA = $absA; | ||
| 524 | $imax = $k; | ||
| 525 | } | ||
| 526 | } | ||
| 527 | |||
| 528 | if ($imax != $i) { | ||
| 529 | |||
| 530 | @P[$i, $imax] = @P[$imax, $i]; | ||
| 531 | @A[$i, $imax] = @A[$imax, $i]; | ||
| 532 | |||
| 533 | ++$P[$N + 1]; | ||
| 534 | } | ||
| 535 | |||
| 536 | foreach my $j ($i + 1 .. $N) { | ||
| 537 | |||
| 538 | if ($A[$i][$i]->is_zero) { | ||
| 539 | return ($N, \@A, \@P); | ||
| 540 | } | ||
| 541 | |||
| 542 | $A[$j][$i] = $A[$j][$i]->div($A[$i][$i]); | ||
| 543 | |||
| 544 | foreach my $k ($i + 1 .. $N) { | ||
| 545 | $A[$j][$k] = $A[$j][$k]->sub($A[$j][$i]->mul($A[$i][$k])); | ||
| 546 | } | ||
| 547 | } | ||
| 548 | } | ||
| 549 | |||
| 550 | return ($N, \@A, \@P); | ||
| 551 | } | ||
| 552 | |||
| 553 | sub solve { | ||
| 554 | my ($self, $vector) = @_; | ||
| 555 | |||
| 556 | my ($N, $A, $P) = $self->_LUP_decompose; | ||
| 557 | |||
| 558 | my @x = map { $vector->[$P->[$_]] } 0 .. $N; | ||
| 559 | |||
| 560 | foreach my $i (1 .. $N) { | ||
| 561 | foreach my $k (0 .. $i - 1) { | ||
| 562 | $x[$i] = $x[$i]->sub($A->[$i][$k]->mul($x[$k])); | ||
| 563 | } | ||
| 564 | } | ||
| 565 | |||
| 566 | for (my $i = $N ; $i >= 0 ; --$i) { | ||
| 567 | foreach my $k ($i + 1 .. $N) { | ||
| 568 | $x[$i] = $x[$i]->sub($A->[$i][$k]->mul($x[$k])); | ||
| 569 | } | ||
| 570 | $x[$i] = $x[$i]->div($A->[$i][$i]); | ||
| 571 | } | ||
| 572 | |||
| 573 | bless(\@x, 'Sidef::Types::Array::Array'); | ||
| 574 | } | ||
| 575 | |||
| 576 | sub invert { | ||
| 577 | my ($self) = @_; | ||
| 578 | |||
| 579 | my ($N, $A, $P) = $self->_LUP_decompose; | ||
| 580 | |||
| 581 | my @I; | ||
| 582 | |||
| 583 | foreach my $j (0 .. $N) { | ||
| 584 | foreach my $i (0 .. $N) { | ||
| 585 | |||
| 586 | $I[$i][$j] = ( | ||
| 587 | ($P->[$i] == $j) | ||
| 588 | ? Sidef::Types::Number::Number::ONE | ||
| 589 | : Sidef::Types::Number::Number::ZERO | ||
| 590 | ); | ||
| 591 | |||
| 592 | foreach my $k (0 .. $i - 1) { | ||
| 593 | $I[$i][$j] = $I[$i][$j]->sub($A->[$i][$k]->mul($I[$k][$j])); | ||
| 594 | } | ||
| 595 | } | ||
| 596 | |||
| 597 | for (my $i = $N ; $i >= 0 ; --$i) { | ||
| 598 | foreach my $k ($i + 1 .. $N) { | ||
| 599 | $I[$i][$j] = $I[$i][$j]->sub($A->[$i][$k]->mul($I[$k][$j])); | ||
| 600 | } | ||
| 601 | |||
| 602 | $I[$i][$j] = $I[$i][$j]->div($A->[$i][$i] // return bless [bless([], 'Sidef::Types::Array::Array')]); | ||
| 603 | } | ||
| 604 | } | ||
| 605 | |||
| 606 | bless($_, 'Sidef::Types::Array::Array') for @I; | ||
| 607 | bless \@I; | ||
| 608 | } | ||
| 609 | |||
| 610 | *inv = \&invert; | ||
| 611 | *inverse = \&invert; | ||
| 612 | |||
| 613 | sub invmod { | ||
| 614 | my ($self, $mod) = @_; | ||
| 615 | |||
| 616 | my $A = $self->inv; | ||
| 617 | |||
| 618 | foreach my $row (@$A) { | ||
| 619 | foreach my $i (0 .. $#{$row}) { | ||
| 620 | $row->[$i] = $row->[$i]->mod($mod); | ||
| 621 | } | ||
| 622 | } | ||
| 623 | |||
| 624 | return $A; | ||
| 625 | } | ||
| 626 | |||
| 627 | sub determinant { | ||
| 628 | my ($self) = @_; | ||
| 629 | |||
| 630 | my ($N, $A, $P) = $self->_LUP_decompose; | ||
| 631 | |||
| 632 | my $det = $A->[0][0] // return Sidef::Types::Number::Number::ONE; | ||
| 633 | |||
| 634 | foreach my $i (1 .. $N) { | ||
| 635 | $det = $det->mul($A->[$i][$i]); | ||
| 636 | } | ||
| 637 | |||
| 638 | if (($P->[$N + 1] - $N) % 2 == 0) { | ||
| 639 | $det = $det->neg; | ||
| 640 | } | ||
| 641 | |||
| 642 | return $det; | ||
| 643 | } | ||
| 644 | |||
| 645 | *det = \&determinant; | ||
| 646 | |||
| 647 | sub trace { | ||
| 648 | my ($self) = @_; | ||
| 649 | Sidef::Types::Number::Number::sum(@{$self->diagonal}); | ||
| 650 | } | ||
| 651 | |||
| 652 | sub is_symmetric { | ||
| 653 | my ($self) = @_; | ||
| 654 | my $n = CORE::int($self->row_count); | ||
| 655 | foreach my $i (0 .. $n - 1) { | ||
| 656 | foreach my $j ($i + 1 .. $n - 1) { | ||
| 657 | $self->[$i][$j]->eq($self->[$j][$i]) | ||
| 658 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 659 | } | ||
| 660 | } | ||
| 661 | Sidef::Types::Bool::Bool::TRUE; | ||
| 662 | } | ||
| 663 | |||
| 664 | sub is_orthogonal { | ||
| 665 | my ($self) = @_; | ||
| 666 | $self->is_square or return Sidef::Types::Bool::Bool::FALSE; | ||
| 667 | my $n = CORE::int($self->row_count); | ||
| 668 | my $product = $self->mul($self->transpose); | ||
| 669 | foreach my $i (0 .. $n - 1) { | ||
| 670 | foreach my $j (0 .. $n - 1) { | ||
| 671 | my $expected = | ||
| 672 | ($i == $j) | ||
| 673 | ? Sidef::Types::Number::Number::ONE | ||
| 674 | : Sidef::Types::Number::Number::ZERO; | ||
| 675 | $product->[$i][$j]->eq($expected) | ||
| 676 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 677 | } | ||
| 678 | } | ||
| 679 | Sidef::Types::Bool::Bool::TRUE; | ||
| 680 | } | ||
| 681 | |||
| 682 | sub is_identity { | ||
| 683 | my ($self) = @_; | ||
| 684 | ($self->is_square && $self->is_diagonal) | ||
| 685 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 686 | foreach my $d (@{$self->diagonal}) { | ||
| 687 | $d->is_one | ||
| 688 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 689 | } | ||
| 690 | Sidef::Types::Bool::Bool::TRUE; | ||
| 691 | } | ||
| 692 | |||
| 693 | sub is_diagonal { | ||
| 694 | my ($self) = @_; | ||
| 695 | my $n = CORE::int($self->row_count); | ||
| 696 | my $m = CORE::int($self->column_count); | ||
| 697 | foreach my $i (0 .. $n - 1) { | ||
| 698 | foreach my $j (0 .. $m - 1) { | ||
| 699 | next if $i == $j; | ||
| 700 | $self->[$i][$j]->is_zero | ||
| 701 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 702 | } | ||
| 703 | } | ||
| 704 | Sidef::Types::Bool::Bool::TRUE; | ||
| 705 | } | ||
| 706 | |||
| 707 | sub is_upper_triangular { | ||
| 708 | my ($self) = @_; | ||
| 709 | my $n = CORE::int($self->row_count); | ||
| 710 | foreach my $i (0 .. $n - 1) { | ||
| 711 | foreach my $j (0 .. $i - 1) { | ||
| 712 | $self->[$i][$j]->is_zero | ||
| 713 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 714 | } | ||
| 715 | } | ||
| 716 | Sidef::Types::Bool::Bool::TRUE; | ||
| 717 | } | ||
| 718 | |||
| 719 | sub is_lower_triangular { | ||
| 720 | my ($self) = @_; | ||
| 721 | my $n = CORE::int($self->row_count); | ||
| 722 | my $m = CORE::int($self->column_count); | ||
| 723 | foreach my $i (0 .. $n - 1) { | ||
| 724 | foreach my $j ($i + 1 .. $m - 1) { | ||
| 725 | $self->[$i][$j]->is_zero | ||
| 726 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 727 | } | ||
| 728 | } | ||
| 729 | Sidef::Types::Bool::Bool::TRUE; | ||
| 730 | } | ||
| 731 | |||
| 732 | sub rank { | ||
| 733 | my ($self) = @_; | ||
| 734 | my $r = $self->rref; | ||
| 735 | my $count = 0; | ||
| 736 | foreach my $row (@$r) { | ||
| 737 | foreach my $value (@$row) { | ||
| 738 | if (!$value->is_zero) { | ||
| 739 | ++$count; | ||
| 740 | last; | ||
| 741 | } | ||
| 742 | } | ||
| 743 | } | ||
| 744 | Sidef::Types::Number::Number::_set_int($count); | ||
| 745 | } | ||
| 746 | |||
| 747 | # Reduced row echelon form | ||
| 748 | sub rref { | ||
| 749 | my ($self) = @_; | ||
| 750 | |||
| 751 | my @m = map { [@$_] } @$self; | ||
| 752 | |||
| 753 | @m || return bless []; | ||
| 754 | |||
| 755 | my ($j, $rows, $cols) = (0, scalar(@m), scalar(@{$m[0]})); | ||
| 756 | |||
| 757 | OUTER: foreach my $r (0 .. $rows - 1) { | ||
| 758 | |||
| 759 | $j < $cols or last; | ||
| 760 | |||
| 761 | my $i = $r; | ||
| 762 | |||
| 763 | while ($m[$i][$j]->is_zero) { | ||
| 764 | ++$i == $rows or next; | ||
| 765 | $i = $r; | ||
| 766 | ++$j == $cols and last OUTER; | ||
| 767 | } | ||
| 768 | |||
| 769 | @m[$i, $r] = @m[$r, $i]; | ||
| 770 | |||
| 771 | my $mr = $m[$r]; | ||
| 772 | my $mrj = $mr->[$j]; | ||
| 773 | |||
| 774 | foreach my $k (0 .. $cols - 1) { | ||
| 775 | $mr->[$k] = $mr->[$k]->div($mrj); | ||
| 776 | } | ||
| 777 | |||
| 778 | foreach my $i (0 .. $rows - 1) { | ||
| 779 | |||
| 780 | $i == $r and next; | ||
| 781 | |||
| 782 | my $mr = $m[$r]; | ||
| 783 | my $mi = $m[$i]; | ||
| 784 | my $mij = $mi->[$j]; | ||
| 785 | |||
| 786 | foreach my $k (0 .. $cols - 1) { | ||
| 787 | $mi->[$k] = $mi->[$k]->sub($mij->mul($mr->[$k])); | ||
| 788 | } | ||
| 789 | } | ||
| 790 | |||
| 791 | ++$j; | ||
| 792 | } | ||
| 793 | |||
| 794 | bless($_, 'Sidef::Types::Array::Array') for @m; | ||
| 795 | bless \@m; | ||
| 796 | } | ||
| 797 | |||
| 798 | *reduced_row_echelon_form = \&rref; | ||
| 799 | |||
| 800 | sub gauss_jordan_invert { | ||
| 801 | my ($self) = @_; | ||
| 802 | |||
| 803 | my $n = $#$self; | ||
| 804 | |||
| 805 | my @I = | ||
| 806 | map { [(Sidef::Types::Number::Number::ZERO) x $_, Sidef::Types::Number::Number::ONE, (Sidef::Types::Number::Number::ZERO) x ($n - $_)] } 0 .. $n; | ||
| 807 | my @A = map { [@{$self->[$_]}, @{$I[$_]}] } 0 .. $n; | ||
| 808 | |||
| 809 | my $r = rref(\@A); | ||
| 810 | @A = map { bless([@{$_}[$n + 1 .. $#$_]], 'Sidef::Types::Array::Array') } @$r; | ||
| 811 | bless \@A; | ||
| 812 | } | ||
| 813 | |||
| 814 | sub gauss_jordan_solve { | ||
| 815 | my ($self, $vector) = @_; | ||
| 816 | |||
| 817 | my @A = map { [@{$self->[$_]}, $vector->[$_]] } 0 .. $#$vector; | ||
| 818 | |||
| 819 | my $r = rref(\@A); | ||
| 820 | bless([map { $_->[-1] } @$r], 'Sidef::Types::Array::Array'); | ||
| 821 | } | ||
| 822 | |||
| 823 | sub det_bareiss { | ||
| 824 | my ($self) = @_; | ||
| 825 | |||
| 826 | my @m = map { [@$_] } @$self; | ||
| 827 | |||
| 828 | my $neg = 0; | ||
| 829 | my $pivot = Sidef::Types::Number::Number::ONE; | ||
| 830 | my $end = $#m; | ||
| 831 | |||
| 832 | foreach my $k (0 .. $end) { | ||
| 833 | my @r = ($k + 1 .. $end); | ||
| 834 | |||
| 835 | my $prev_pivot = $pivot; | ||
| 836 | $pivot = $m[$k][$k] // return Sidef::Types::Number::Number::ONE; | ||
| 837 | |||
| 838 | if ($pivot->is_zero) { | ||
| 839 | my $i = List::Util::first(sub { $m[$_][$k] }, @r) // return Sidef::Types::Number::Number::ZERO; | ||
| 840 | @m[$i, $k] = @m[$k, $i]; | ||
| 841 | $pivot = $m[$k][$k]; | ||
| 842 | $neg ^= 1; | ||
| 843 | } | ||
| 844 | |||
| 845 | foreach my $i (@r) { | ||
| 846 | foreach my $j (@r) { | ||
| 847 | $m[$i][$j] = $m[$i][$j]->mul($pivot); | ||
| 848 | $m[$i][$j] = $m[$i][$j]->sub($m[$i][$k]->mul($m[$k][$j])); | ||
| 849 | $m[$i][$j] = $m[$i][$j]->div($prev_pivot); | ||
| 850 | } | ||
| 851 | } | ||
| 852 | } | ||
| 853 | |||
| 854 | $neg ? $pivot->neg : $pivot; | ||
| 855 | } | ||
| 856 | |||
| 857 | sub transpose { | ||
| 858 | my ($matrix) = @_; | ||
| 859 | bless($matrix->SUPER::transpose); | ||
| 860 | } | ||
| 861 | |||
| 862 | *t = \&transpose; | ||
| 863 | *not = \&transpose; | ||
| 864 | |||
| 865 | sub concat { | ||
| 866 | my ($m1, $m2) = @_; | ||
| 867 | |||
| 868 | if (_is_matrix($m2)) { | ||
| 869 | |||
| 870 | my $end = List::Util::min($#{$m1}, $#{$m2}); | ||
| 871 | |||
| 872 | my @m3; | ||
| 873 | foreach my $i (0 .. $end) { | ||
| 874 | push @m3, bless [@{$m1->[$i]}, @{$m2->[$i]}], 'Sidef::Types::Array::Array'; | ||
| 875 | } | ||
| 876 | |||
| 877 | return bless \@m3; | ||
| 878 | } | ||
| 879 | |||
| 880 | # Scalar concatenation | ||
| 881 | my @m3; | ||
| 882 | foreach my $i (0 .. $#{$m1}) { | ||
| 883 | push @m3, bless [@{$m1->[$i]}, $m2], 'Sidef::Types::Array::Array'; | ||
| 884 | } | ||
| 885 | |||
| 886 | bless \@m3; | ||
| 887 | } | ||
| 888 | |||
| 889 | sub horizontal_flip { | ||
| 890 | my ($self) = @_; | ||
| 891 | bless [map { bless [reverse(@$_)], 'Sidef::Types::Array::Array' } @{$self}]; | ||
| 892 | } | ||
| 893 | |||
| 894 | sub vertical_flip { | ||
| 895 | my ($self) = @_; | ||
| 896 | bless [reverse @{$self}]; | ||
| 897 | } | ||
| 898 | |||
| 899 | sub flip { | ||
| 900 | my ($self) = @_; | ||
| 901 | bless [reverse map { bless [reverse(@$_)], 'Sidef::Types::Array::Array' } @{$self}]; | ||
| 902 | } | ||
| 903 | |||
| 904 | sub set_row { | ||
| 905 | my ($A, $k, $row) = @_; | ||
| 906 | $k = CORE::int($k); | ||
| 907 | $A->[$k] = bless([@$row], 'Sidef::Types::Array::Array'); | ||
| 908 | $A; | ||
| 909 | } | ||
| 910 | |||
| 911 | sub set_column { | ||
| 912 | my ($A, $k, $col) = @_; | ||
| 913 | |||
| 914 | $k = CORE::int($k); | ||
| 915 | |||
| 916 | foreach my $i (0 .. $#{$col}) { | ||
| 917 | $A->[$i][$k] = $col->[$i]; | ||
| 918 | } | ||
| 919 | |||
| 920 | $A; | ||
| 921 | } | ||
| 922 | |||
| 923 | *set_col = \&set_column; | ||
| 924 | |||
| 925 | sub column_count { | ||
| 926 | my ($A) = @_; | ||
| 927 | @$A || return Sidef::Types::Number::Number::ZERO; | ||
| 928 | Sidef::Types::Number::Number::_set_int(scalar @{$A->[0]}); | ||
| 929 | } | ||
| 930 | |||
| 931 | *column_len = \&column_count; | ||
| 932 | *column_size = \&column_count; | ||
| 933 | *col_size = \&column_count; | ||
| 934 | *col_count = \&column_count; | ||
| 935 | *col_len = \&column_count; | ||
| 936 | |||
| 937 | sub row_count { | ||
| 938 | my ($A) = @_; | ||
| 939 | Sidef::Types::Number::Number::_set_int(scalar @$A); | ||
| 940 | } | ||
| 941 | |||
| 942 | *row_len = \&row_count; | ||
| 943 | *row_size = \&row_count; | ||
| 944 | |||
| 945 | sub to_array { | ||
| 946 | my ($A) = @_; | ||
| 947 | Sidef::Types::Array::Array->new(@$A); | ||
| 948 | } | ||
| 949 | |||
| 950 | *to_a = \&to_array; | ||
| 951 | |||
| 952 | sub _dump { | ||
| 953 | "Matrix(\n " . join(",\n ", @{$_[0]}) . "\n)"; | ||
| 954 | } | ||
| 955 | |||
| 956 | sub dump { | ||
| 957 | Sidef::Types::String::String->new($_[0]->_dump); | ||
| 958 | } | ||
| 959 | |||
| 960 | *to_s = \&dump; | ||
| 961 | *to_str = \&dump; | ||
| 962 | |||
| 963 | { | ||
| 964 | no strict 'refs'; | ||
| 965 | |||
| 966 | *{__PACKAGE__ . '::' . '*'} = \&mul; | ||
| 967 | *{__PACKAGE__ . '::' . '**'} = \&pow; | ||
| 968 | *{__PACKAGE__ . '::' . '+'} = \&add; | ||
| 969 | *{__PACKAGE__ . '::' . '-'} = \⊂ | ||
| 970 | *{__PACKAGE__ . '::' . '/'} = \÷ | ||
| 971 | *{__PACKAGE__ . '::' . 'รท'} = \÷ | ||
| 972 | *{__PACKAGE__ . '::' . '&'} = \∧ | ||
| 973 | *{__PACKAGE__ . '::' . '|'} = \∨ | ||
| 974 | *{__PACKAGE__ . '::' . '^'} = \&xor; | ||
| 975 | *{__PACKAGE__ . '::' . '%'} = \&mod; | ||
| 976 | } | ||
| 977 | |||
| 978 | 1 |