1use std::collections::HashMap;
2
3use super::computation::*;
4use super::core_types::*;
5use super::storage::AccessPattern;
6
7pub struct OptimizationEngine {
9 pub optimizer: MatrixOptimizer,
10 pub analyzer: MatrixAnalyzer,
11 pub transformer: MatrixTransformer,
12}
13
14pub struct MatrixOptimizer {
16 pub optimization_strategies: Vec<OptimizationStrategy>,
17 pub optimization_history: Vec<OptimizationRecord>,
18}
19
20#[derive(Debug, Clone, PartialEq)]
22pub enum OptimizationStrategy {
23 CacheOptimization,
24 MemoryLayoutOptimization,
25 AlgorithmSelection,
26 Parallelization,
27 Vectorization,
28 Fusion,
29}
30
31#[derive(Debug, Clone)]
33pub struct OptimizationRecord {
34 pub timestamp: u64,
35 pub matrix_id: String,
36 pub strategy: OptimizationStrategy,
37 pub performance_improvement: f64,
38 pub memory_reduction: f64,
39}
40
41pub struct MatrixAnalyzer {
43 pub analysis_algorithms: Vec<AnalysisAlgorithm>,
44 pub pattern_recognition: PatternRecognition,
45}
46
47#[derive(Debug, Clone, PartialEq)]
49pub enum AnalysisAlgorithm {
50 SparsityAnalysis,
51 StructureAnalysis,
52 AccessPatternAnalysis,
53 PerformanceAnalysis,
54}
55
56pub struct PatternRecognition {
58 pub recognized_patterns: Vec<MatrixPattern>,
59 pub pattern_library: PatternLibrary,
60}
61
62#[derive(Debug, Clone, PartialEq, Eq, Hash)]
64pub enum MatrixPattern {
65 Diagonal,
66 Triangular,
67 Banded,
68 Symmetric,
69 PositiveDefinite,
70 Orthogonal,
71 Sparse,
72 Dense,
73 BlockDiagonal,
74 Toeplitz,
75 Hankel,
76 Circulant,
77}
78
79pub struct PatternLibrary {
81 pub patterns: HashMap<String, MatrixPattern>,
82 pub optimization_hints: HashMap<MatrixPattern, OptimizationHint>,
83}
84
85#[derive(Debug, Clone)]
87pub struct OptimizationHint {
88 pub preferred_algorithm: String,
89 pub memory_layout: StorageFormat,
90 pub parallelization_strategy: String,
91 pub vectorization_hints: Vec<String>,
92 pub estimated_speedup: f64,
94}
95
96pub struct MatrixTransformer {
98 pub transformation_rules: Vec<TransformationRule>,
99 pub transformation_history: Vec<TransformationRecord>,
100}
101
102#[derive(Debug, Clone, PartialEq)]
104pub enum TransformationRule {
105 RowColumnSwap,
106 BlockReordering,
107 DataTypeConversion,
108 CompressionDecompression,
109 LayoutConversion,
110}
111
112#[derive(Debug, Clone)]
114pub struct TransformationRecord {
115 pub timestamp: u64,
116 pub matrix_id: String,
117 pub transformation: TransformationRule,
118 pub performance_impact: f64,
119}
120
121#[derive(Debug, Clone, PartialEq)]
128pub enum MatrixLayout {
129 RowMajor,
133 ColMajor,
136 Blocked(Box<MatrixLayout>, usize),
144 Packed,
149}
150
151const SIMD_WIDTH: usize = 4;
155
156impl OptimizationEngine {
157 pub fn new() -> Self {
160 Self {
161 optimizer: MatrixOptimizer::new(),
162 analyzer: MatrixAnalyzer::new(),
163 transformer: MatrixTransformer::new(),
164 }
165 }
166
167 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
169 self.optimizer.initialize()?;
170 self.analyzer.initialize()?;
171 self.transformer.initialize()?;
172 Ok(())
173 }
174
175 pub fn optimize_multiplication(
181 &mut self,
182 left: &Matrix,
183 right: &Matrix,
184 ) -> Result<OptimizedMultiplication, LinearAlgebraError> {
185 let left_analysis = self.analyzer.analyze_matrix(left)?;
186 let right_analysis = self.analyzer.analyze_matrix(right)?;
187
188 let max_sparsity = left_analysis.sparsity.max(right_analysis.sparsity);
189 let total_flops = (left.rows * left.cols * right.cols) as f64;
190
191 let mut best_hint: Option<(MatrixPattern, OptimizationHint)> = None;
193 for pat in left_analysis
194 .detected_patterns
195 .iter()
196 .chain(right_analysis.detected_patterns.iter())
197 {
198 if *pat != MatrixPattern::Dense {
199 if let Some(hint) = self
200 .analyzer
201 .pattern_recognition
202 .pattern_library
203 .get_optimization_hint(pat)
204 {
205 if let Some((_, ref current_best)) = best_hint {
206 if hint.estimated_speedup > current_best.estimated_speedup {
207 best_hint = Some((pat.clone(), hint.clone()));
208 }
209 } else {
210 best_hint = Some((pat.clone(), hint.clone()));
211 }
212 }
213 }
214 }
215
216 let (candidate_strategy, candidate_gain) = if let Some((pattern, hint)) = best_hint {
217 let gain = if pattern == MatrixPattern::Sparse {
219 (1.0 / (1.0 - max_sparsity)).max(hint.estimated_speedup).min(15.0)
220 } else {
221 hint.estimated_speedup
222 };
223 (OptimizationStrategy::AlgorithmSelection, gain)
224 } else if max_sparsity >= 0.70 {
225 let gain = (1.0 / (1.0 - max_sparsity)).min(15.0);
227 (OptimizationStrategy::AlgorithmSelection, gain)
228 } else if total_flops >= 1024.0 * 1024.0 || left.rows >= 512 {
229 let cores = num_cpus::get().min(8) as f64;
231 let gain = (cores * 0.75).max(1.5);
232 (OptimizationStrategy::Parallelization, gain)
233 } else if left.rows >= 64 && left.cols >= 64 {
234 (OptimizationStrategy::CacheOptimization, 2.5)
236 } else {
237 let simd_width = match left.metadata.data_type {
239 DataType::Float32 => 4.0, DataType::Float64 => 2.0, _ => 2.0,
242 };
243 (OptimizationStrategy::Vectorization, simd_width)
244 };
245
246 let fallbacks = [
248 OptimizationStrategy::CacheOptimization,
249 OptimizationStrategy::Vectorization,
250 OptimizationStrategy::Parallelization,
251 OptimizationStrategy::AlgorithmSelection,
252 OptimizationStrategy::MemoryLayoutOptimization,
253 ];
254 let strategy = self
255 .optimizer
256 .resolve_strategy(candidate_strategy.clone(), &fallbacks)?;
257
258 let expected_gain = if strategy == candidate_strategy {
259 candidate_gain
260 } else {
261 match strategy {
263 OptimizationStrategy::AlgorithmSelection => 3.0,
264 OptimizationStrategy::Parallelization => (num_cpus::get().min(8) as f64 * 0.75).max(1.5),
265 OptimizationStrategy::CacheOptimization => 2.5,
266 OptimizationStrategy::Vectorization => 2.0,
267 OptimizationStrategy::MemoryLayoutOptimization => 1.8,
268 OptimizationStrategy::Fusion => 2.0,
269 }
270 };
271
272 let timestamp = std::time::SystemTime::now()
274 .duration_since(std::time::UNIX_EPOCH)
275 .unwrap_or_default()
276 .as_secs();
277 self.optimizer.optimization_history.push(OptimizationRecord {
278 timestamp,
279 matrix_id: format!("{}_x_{}", left.matrix_id, right.matrix_id),
280 strategy: strategy.clone(),
281 performance_improvement: expected_gain,
282 memory_reduction: if strategy == OptimizationStrategy::AlgorithmSelection {
283 max_sparsity * 100.0
284 } else {
285 0.0
286 },
287 });
288
289 let optimized = OptimizedMultiplication {
291 left: left.clone(),
292 right: right.clone(),
293 optimization_strategy: strategy,
294 expected_performance_gain: expected_gain,
295 };
296
297 Ok(optimized)
298 }
299}
300
301impl MatrixOptimizer {
302 pub fn new() -> Self {
304 Self {
305 optimization_strategies: vec![
306 OptimizationStrategy::AlgorithmSelection,
307 OptimizationStrategy::Vectorization,
308 OptimizationStrategy::CacheOptimization,
309 OptimizationStrategy::Parallelization,
310 OptimizationStrategy::MemoryLayoutOptimization,
311 OptimizationStrategy::Fusion,
312 ],
313 optimization_history: Vec::new(),
314 }
315 }
316
317 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
319 Ok(())
320 }
321
322 pub fn register_strategy(&mut self, strategy: OptimizationStrategy) {
324 if !self.optimization_strategies.contains(&strategy) {
325 self.optimization_strategies.push(strategy);
326 }
327 }
328
329 pub fn unregister_strategy(&mut self, strategy: &OptimizationStrategy) {
331 self.optimization_strategies.retain(|s| s != strategy);
332 }
333
334 pub fn is_strategy_enabled(&self, strategy: &OptimizationStrategy) -> bool {
336 self.optimization_strategies.contains(strategy)
337 }
338
339 pub fn resolve_strategy(
343 &self,
344 preferred: OptimizationStrategy,
345 fallbacks: &[OptimizationStrategy],
346 ) -> Result<OptimizationStrategy, LinearAlgebraError> {
347 if self.is_strategy_enabled(&preferred) {
348 return Ok(preferred);
349 }
350 for fallback in fallbacks {
351 if self.is_strategy_enabled(fallback) {
352 return Ok(fallback.clone());
353 }
354 }
355 if let Some(first) = self.optimization_strategies.first() {
356 return Ok(first.clone());
357 }
358 Err(LinearAlgebraError::OptimizationError(
359 "No optimization strategies are enabled in MatrixOptimizer".to_string(),
360 ))
361 }
362}
363
364impl MatrixAnalyzer {
365 pub fn new() -> Self {
368 Self {
369 analysis_algorithms: vec![
370 AnalysisAlgorithm::StructureAnalysis,
371 AnalysisAlgorithm::SparsityAnalysis,
372 ],
373 pattern_recognition: PatternRecognition::new(),
374 }
375 }
376
377 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
380 self.pattern_recognition.initialize()?;
381 Ok(())
382 }
383
384 pub fn analyze_matrix(
387 &mut self,
388 matrix: &Matrix,
389 ) -> Result<MatrixAnalysis, LinearAlgebraError> {
390 let detected = self.detect_structure(matrix);
391 let sparsity = self.calculate_sparsity(matrix);
392
393 for pattern in &detected {
395 if !self.pattern_recognition.recognized_patterns.contains(pattern) {
396 self.pattern_recognition.recognized_patterns.push(pattern.clone());
397 }
398 }
399
400 let mut recommended_algorithms = Vec::new();
402 let mut hint_strings = Vec::new();
403 for pattern in &detected {
404 if let Some(hint) = self
405 .pattern_recognition
406 .pattern_library
407 .get_optimization_hint(pattern)
408 {
409 recommended_algorithms.push(hint.preferred_algorithm.clone());
410 hint_strings.push(format!(
411 "{:?}: {} (speedup ~{:.1}x)",
412 pattern, hint.preferred_algorithm, hint.estimated_speedup
413 ));
414 }
415 }
416
417 let structure = detected.first().cloned().unwrap_or(MatrixPattern::Dense);
419
420 Ok(MatrixAnalysis {
421 matrix_id: matrix.matrix_id.clone(),
422 sparsity,
423 structure,
424 detected_patterns: detected,
425 access_pattern: AccessPattern::Sequential,
426 optimization_hints: hint_strings,
427 recommended_algorithms,
428 })
429 }
430
431 fn calculate_sparsity(&self, matrix: &Matrix) -> f64 {
434 let non_zero = matrix.data.iter().filter(|&&x| x.abs() > 1e-10).count();
435 1.0 - (non_zero as f64 / matrix.data.len().max(1) as f64)
436 }
437
438 pub fn detect_structure(&self, matrix: &Matrix) -> Vec<MatrixPattern> {
441 const TOL: f64 = 1e-10;
442 let rows = matrix.rows;
443 let cols = matrix.cols;
444 let data = &matrix.data;
445 let mut patterns = Vec::new();
446
447 let at = |i: usize, j: usize| -> f64 { data[i * cols + j] };
449
450 let non_zero_count = data.iter().filter(|&&x| x.abs() > TOL).count();
452 let total = data.len();
453 let non_zero_frac = if total > 0 {
454 non_zero_count as f64 / total as f64
455 } else {
456 0.0
457 };
458 let is_sparse = non_zero_frac < 0.3;
459 if is_sparse {
460 patterns.push(MatrixPattern::Sparse);
461 }
462
463 let is_square = rows == cols && rows > 0;
465
466 if is_square {
468 let mut is_diagonal = true;
469 for i in 0..rows {
470 for j in 0..cols {
471 if i != j && at(i, j).abs() > TOL {
472 is_diagonal = false;
473 break;
474 }
475 }
476 if !is_diagonal {
477 break;
478 }
479 }
480 if is_diagonal {
481 patterns.push(MatrixPattern::Diagonal);
482 }
483 }
484
485 if is_square {
487 let mut is_upper = true;
489 for i in 1..rows {
490 for j in 0..i {
491 if at(i, j).abs() > TOL {
492 is_upper = false;
493 break;
494 }
495 }
496 if !is_upper {
497 break;
498 }
499 }
500 let mut is_lower = true;
502 for i in 0..rows {
503 for j in (i + 1)..cols {
504 if at(i, j).abs() > TOL {
505 is_lower = false;
506 break;
507 }
508 }
509 if !is_lower {
510 break;
511 }
512 }
513 if is_upper || is_lower {
514 patterns.push(MatrixPattern::Triangular);
515 }
516 }
517
518 if is_square {
520 let mut is_symmetric = true;
521 for i in 0..rows {
522 for j in (i + 1)..cols {
523 if (at(i, j) - at(j, i)).abs() > TOL {
524 is_symmetric = false;
525 break;
526 }
527 }
528 if !is_symmetric {
529 break;
530 }
531 }
532 if is_symmetric {
533 patterns.push(MatrixPattern::Symmetric);
534
535 if Self::is_positive_definite(rows, data, TOL) {
538 patterns.push(MatrixPattern::PositiveDefinite);
539 }
540 }
541 }
542
543 if rows > 0 && cols > 0 {
545 let max_dim = rows.max(cols);
546 let mut bandwidth = 0usize;
548 for i in 0..rows {
549 for j in 0..cols {
550 if at(i, j).abs() > TOL {
551 let dist = if i >= j { i - j } else { j - i };
552 if dist > bandwidth {
553 bandwidth = dist;
554 }
555 }
556 }
557 }
558 if bandwidth > 0 && (bandwidth as f64) < (max_dim as f64) / 3.0 {
561 patterns.push(MatrixPattern::Banded);
562 }
563 }
564
565 if is_square && rows >= 4 {
567 if Self::is_block_diagonal(rows, data, TOL) {
568 patterns.push(MatrixPattern::BlockDiagonal);
569 }
570 }
571
572 if rows > 1 && cols > 1 {
574 let mut is_toeplitz = true;
575 for d in -(rows as isize - 1)..(cols as isize) {
577 let first = if d >= 0 {
579 at(0, d as usize)
580 } else {
581 at((-d) as usize, 0)
582 };
583 let start_i = if d >= 0 { 0 } else { (-d) as usize };
585 let start_j = if d >= 0 { d as usize } else { 0 };
586 let mut i = start_i;
587 let mut j = start_j;
588 while i < rows && j < cols {
589 if (at(i, j) - first).abs() > TOL {
590 is_toeplitz = false;
591 break;
592 }
593 i += 1;
594 j += 1;
595 }
596 if !is_toeplitz {
597 break;
598 }
599 }
600 if is_toeplitz {
601 patterns.push(MatrixPattern::Toeplitz);
602 }
603 }
604
605 if is_square && rows > 0 {
607 if Self::is_orthogonal(rows, data, TOL) {
608 patterns.push(MatrixPattern::Orthogonal);
609 }
610 }
611
612 if is_square && rows > 1 {
614 let mut is_circulant = true;
615 for i in 1..rows {
616 for j in 0..cols {
618 let expected = at(i - 1, if j == 0 { cols - 1 } else { j - 1 });
619 if (at(i, j) - expected).abs() > TOL {
620 is_circulant = false;
621 break;
622 }
623 }
624 if !is_circulant {
625 break;
626 }
627 }
628 if is_circulant {
629 patterns.push(MatrixPattern::Circulant);
630 }
631 }
632
633 if rows > 1 && cols > 1 {
635 let mut is_hankel = true;
636 for d in 0..(rows + cols - 1) {
639 let mut first_val: Option<f64> = None;
641 for i in 0..rows {
642 let j = d as isize - i as isize;
643 if j >= 0 && (j as usize) < cols {
644 let v = at(i, j as usize);
645 if first_val.is_none() {
646 first_val = Some(v);
647 } else if (v - first_val.unwrap()).abs() > TOL {
648 is_hankel = false;
649 break;
650 }
651 }
652 }
653 if !is_hankel {
654 break;
655 }
656 }
657 if is_hankel {
658 patterns.push(MatrixPattern::Hankel);
659 }
660 }
661
662 if patterns.is_empty() {
664 patterns.push(MatrixPattern::Dense);
665 }
666
667 patterns
668 }
669
670 fn is_positive_definite(n: usize, data: &[f64], tol: f64) -> bool {
673 for k in 1..=n {
674 let mut sub = vec![0.0; k * k];
676 for i in 0..k {
677 for j in 0..k {
678 sub[i * k + j] = data[i * n + j];
679 }
680 }
681 let det = Self::determinant(k, &sub);
683 if det <= tol {
684 return false;
685 }
686 }
687 true
688 }
689
690 fn determinant(n: usize, data: &[f64]) -> f64 {
692 if n == 0 {
693 return 1.0;
694 }
695 if n == 1 {
696 return data[0];
697 }
698 let mut a = data.to_vec();
700 let mut sign = 1.0_f64;
701 for i in 0..n {
702 let mut max_row = i;
704 let mut max_val = a[i * n + i].abs();
705 for k in (i + 1)..n {
706 if a[k * n + i].abs() > max_val {
707 max_val = a[k * n + i].abs();
708 max_row = k;
709 }
710 }
711 if max_val < 1e-15 {
712 return 0.0; }
714 if max_row != i {
715 for j in 0..n {
716 let tmp = a[i * n + j];
717 a[i * n + j] = a[max_row * n + j];
718 a[max_row * n + j] = tmp;
719 }
720 sign = -sign;
721 }
722 for k in (i + 1)..n {
724 let factor = a[k * n + i] / a[i * n + i];
725 for j in i..n {
726 a[k * n + j] -= factor * a[i * n + j];
727 }
728 }
729 }
730 let mut det = sign;
731 for i in 0..n {
732 det *= a[i * n + i];
733 }
734 det
735 }
736
737 fn is_block_diagonal(n: usize, data: &[f64], tol: f64) -> bool {
739 let at = |i: usize, j: usize| -> f64 { data[i * n + j] };
742 for block_size in [2, 4, 8].iter() {
743 if *block_size >= n {
744 continue;
745 }
746 if n % block_size != 0 {
747 continue;
748 }
749 let mut is_block_diag = true;
750 'outer: for bi in 0..(n / block_size) {
751 for bj in 0..(n / block_size) {
752 if bi == bj {
753 continue; }
755 for i in 0..*block_size {
757 for j in 0..*block_size {
758 if at(bi * block_size + i, bj * block_size + j).abs() > tol {
759 is_block_diag = false;
760 break 'outer;
761 }
762 }
763 }
764 }
765 }
766 if is_block_diag {
767 return true;
768 }
769 }
770 false
771 }
772
773 fn is_orthogonal(n: usize, data: &[f64], tol: f64) -> bool {
775 let at = |i: usize, j: usize| -> f64 { data[i * n + j] };
776 for i in 0..n {
778 for j in 0..n {
779 let mut dot = 0.0;
780 for k in 0..n {
781 dot += at(i, k) * at(j, k);
782 }
783 let expected = if i == j { 1.0 } else { 0.0 };
784 if (dot - expected).abs() > tol * 10.0 {
785 return false;
786 }
787 }
788 }
789 true
790 }
791}
792
793impl PatternRecognition {
794 pub fn new() -> Self {
797 Self {
798 recognized_patterns: Vec::new(),
799 pattern_library: PatternLibrary::new(),
800 }
801 }
802
803 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
805 self.pattern_library.initialize()?;
806 Ok(())
807 }
808}
809
810impl PatternLibrary {
811 pub fn new() -> Self {
814 Self {
815 patterns: HashMap::new(),
816 optimization_hints: HashMap::new(),
817 }
818 }
819
820 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
823 self.patterns
825 .insert("diagonal".to_string(), MatrixPattern::Diagonal);
826 self.patterns
827 .insert("triangular".to_string(), MatrixPattern::Triangular);
828 self.patterns
829 .insert("banded".to_string(), MatrixPattern::Banded);
830 self.patterns
831 .insert("symmetric".to_string(), MatrixPattern::Symmetric);
832 self.patterns.insert(
833 "positive_definite".to_string(),
834 MatrixPattern::PositiveDefinite,
835 );
836 self.patterns
837 .insert("orthogonal".to_string(), MatrixPattern::Orthogonal);
838 self.patterns
839 .insert("sparse".to_string(), MatrixPattern::Sparse);
840 self.patterns
841 .insert("dense".to_string(), MatrixPattern::Dense);
842 self.patterns
843 .insert("block_diagonal".to_string(), MatrixPattern::BlockDiagonal);
844 self.patterns
845 .insert("toeplitz".to_string(), MatrixPattern::Toeplitz);
846 self.patterns
847 .insert("hankel".to_string(), MatrixPattern::Hankel);
848 self.patterns
849 .insert("circulant".to_string(), MatrixPattern::Circulant);
850
851 self.optimization_hints.insert(
853 MatrixPattern::Diagonal,
854 OptimizationHint {
855 preferred_algorithm: "diagonal_scale".to_string(),
856 memory_layout: StorageFormat::CompressedSparseRow,
857 parallelization_strategy: "element_wise".to_string(),
858 vectorization_hints: vec!["scalar_multiply".to_string()],
859 estimated_speedup: 10.0,
860 },
861 );
862 self.optimization_hints.insert(
863 MatrixPattern::Triangular,
864 OptimizationHint {
865 preferred_algorithm: "triangular_solve".to_string(),
866 memory_layout: StorageFormat::RowMajor,
867 parallelization_strategy: "row_parallel".to_string(),
868 vectorization_hints: vec!["forward_substitution".to_string()],
869 estimated_speedup: 3.0,
870 },
871 );
872 self.optimization_hints.insert(
873 MatrixPattern::Banded,
874 OptimizationHint {
875 preferred_algorithm: "banded_gemm".to_string(),
876 memory_layout: StorageFormat::Blocked,
877 parallelization_strategy: "band_parallel".to_string(),
878 vectorization_hints: vec!["band_vectorization".to_string()],
879 estimated_speedup: 5.0,
880 },
881 );
882 self.optimization_hints.insert(
883 MatrixPattern::Symmetric,
884 OptimizationHint {
885 preferred_algorithm: "symmetric_gemm".to_string(),
886 memory_layout: StorageFormat::RowMajor,
887 parallelization_strategy: "block_parallel".to_string(),
888 vectorization_hints: vec!["symmetric_pack".to_string()],
889 estimated_speedup: 2.0,
890 },
891 );
892 self.optimization_hints.insert(
893 MatrixPattern::PositiveDefinite,
894 OptimizationHint {
895 preferred_algorithm: "cholesky_decomposition".to_string(),
896 memory_layout: StorageFormat::RowMajor,
897 parallelization_strategy: "block_parallel".to_string(),
898 vectorization_hints: vec!["cholesky_vectorized".to_string()],
899 estimated_speedup: 4.0,
900 },
901 );
902 self.optimization_hints.insert(
903 MatrixPattern::Orthogonal,
904 OptimizationHint {
905 preferred_algorithm: "orthogonal_transform".to_string(),
906 memory_layout: StorageFormat::RowMajor,
907 parallelization_strategy: "column_parallel".to_string(),
908 vectorization_hints: vec!["transpose_free".to_string()],
909 estimated_speedup: 3.0,
910 },
911 );
912 self.optimization_hints.insert(
913 MatrixPattern::Sparse,
914 OptimizationHint {
915 preferred_algorithm: "sparse_gemm".to_string(),
916 memory_layout: StorageFormat::CompressedSparseRow,
917 parallelization_strategy: "row_parallel".to_string(),
918 vectorization_hints: vec!["sparse_vectorization".to_string()],
919 estimated_speedup: 8.0,
920 },
921 );
922 self.optimization_hints.insert(
923 MatrixPattern::Dense,
924 OptimizationHint {
925 preferred_algorithm: "blocked_gemm".to_string(),
926 memory_layout: StorageFormat::Blocked,
927 parallelization_strategy: "block_parallel".to_string(),
928 vectorization_hints: vec!["avx2_vectorization".to_string()],
929 estimated_speedup: 1.0,
930 },
931 );
932 self.optimization_hints.insert(
933 MatrixPattern::BlockDiagonal,
934 OptimizationHint {
935 preferred_algorithm: "block_diagonal_gemm".to_string(),
936 memory_layout: StorageFormat::Blocked,
937 parallelization_strategy: "block_parallel".to_string(),
938 vectorization_hints: vec!["block_vectorization".to_string()],
939 estimated_speedup: 6.0,
940 },
941 );
942 self.optimization_hints.insert(
943 MatrixPattern::Toeplitz,
944 OptimizationHint {
945 preferred_algorithm: "toeplitz_fft".to_string(),
946 memory_layout: StorageFormat::RowMajor,
947 parallelization_strategy: "diagonal_parallel".to_string(),
948 vectorization_hints: vec!["fft_convolution".to_string()],
949 estimated_speedup: 7.0,
950 },
951 );
952 self.optimization_hints.insert(
953 MatrixPattern::Hankel,
954 OptimizationHint {
955 preferred_algorithm: "hankel_fft".to_string(),
956 memory_layout: StorageFormat::RowMajor,
957 parallelization_strategy: "anti_diagonal_parallel".to_string(),
958 vectorization_hints: vec!["fft_convolution".to_string()],
959 estimated_speedup: 7.0,
960 },
961 );
962 self.optimization_hints.insert(
963 MatrixPattern::Circulant,
964 OptimizationHint {
965 preferred_algorithm: "circulant_fft".to_string(),
966 memory_layout: StorageFormat::RowMajor,
967 parallelization_strategy: "row_parallel".to_string(),
968 vectorization_hints: vec!["fft_convolution".to_string()],
969 estimated_speedup: 8.0,
970 },
971 );
972
973 Ok(())
974 }
975
976 pub fn get_optimization_hint(&self, pattern: &MatrixPattern) -> Option<&OptimizationHint> {
978 self.optimization_hints.get(pattern)
979 }
980}
981
982impl MatrixTransformer {
983 pub fn new() -> Self {
987 Self {
988 transformation_rules: vec![
989 TransformationRule::LayoutConversion,
990 TransformationRule::RowColumnSwap,
991 TransformationRule::BlockReordering,
992 TransformationRule::DataTypeConversion,
993 ],
994 transformation_history: Vec::new(),
995 }
996 }
997
998 pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
1000 Ok(())
1001 }
1002
1003 pub fn transform_matrix(
1020 &self,
1021 matrix: &Matrix,
1022 target_layout: MatrixLayout,
1023 ) -> Result<Matrix, LinearAlgebraError> {
1024 let rows = matrix.rows;
1025 let cols = matrix.cols;
1026
1027 validate_source_buffer(matrix)?;
1029
1030 let src =
1033 |i: usize, j: usize| -> Result<f64, LinearAlgebraError> { read_element(matrix, i, j) };
1034
1035 let (data, storage_format) = match target_layout {
1036 MatrixLayout::RowMajor => {
1037 let mut data = Vec::with_capacity(rows * cols);
1038 for i in 0..rows {
1039 for j in 0..cols {
1040 data.push(src(i, j)?);
1041 }
1042 }
1043 (data, StorageFormat::RowMajor)
1044 }
1045 MatrixLayout::ColMajor => {
1046 let mut data = Vec::with_capacity(rows * cols);
1047 for j in 0..cols {
1049 for i in 0..rows {
1050 data.push(src(i, j)?);
1051 }
1052 }
1053 (data, StorageFormat::ColumnMajor)
1054 }
1055 MatrixLayout::Blocked(inner, block_size) => {
1056 if block_size == 0 {
1057 return Err(LinearAlgebraError::OptimizationError(
1058 "Blocked layout requires block_size > 0".to_string(),
1059 ));
1060 }
1061 let mut data = Vec::with_capacity(rows * cols);
1062 let block_rows = (rows + block_size - 1) / block_size;
1063 let block_cols = (cols + block_size - 1) / block_size;
1064 let col_major_inner = *inner == MatrixLayout::ColMajor;
1067 for bi in 0..block_rows {
1068 for bj in 0..block_cols {
1069 let i_start = bi * block_size;
1070 let i_end = rows.min((bi + 1) * block_size);
1071 let j_start = bj * block_size;
1072 let j_end = cols.min((bj + 1) * block_size);
1073 if col_major_inner {
1074 for j in j_start..j_end {
1075 for i in i_start..i_end {
1076 data.push(src(i, j)?);
1077 }
1078 }
1079 } else {
1080 for i in i_start..i_end {
1081 for j in j_start..j_end {
1082 data.push(src(i, j)?);
1083 }
1084 }
1085 }
1086 }
1087 }
1088 (data, StorageFormat::Blocked)
1089 }
1090 MatrixLayout::Packed => {
1091 let stride = padded_stride(cols);
1092 let mut data = vec![0.0; rows * stride];
1093 for i in 0..rows {
1094 for j in 0..cols {
1095 data[i * stride + j] = src(i, j)?;
1096 }
1097 }
1098 (data, StorageFormat::Packed)
1099 }
1100 };
1101
1102 let mut result = matrix.clone();
1103 result.data = data;
1104 result.storage_format = storage_format.clone();
1105 result.metadata.storage_format = storage_format;
1106 Ok(result)
1107 }
1108
1109 pub fn optimize_layout(
1122 &self,
1123 matrix: &Matrix,
1124 access_pattern: &AccessPattern,
1125 ) -> Result<Matrix, LinearAlgebraError> {
1126 let target = match access_pattern {
1127 AccessPattern::Sequential => MatrixLayout::RowMajor,
1128 AccessPattern::Strided => MatrixLayout::ColMajor,
1129 AccessPattern::Blocked => {
1130 let block_size = matrix.rows.min(matrix.cols).max(1).min(16);
1133 MatrixLayout::Blocked(Box::new(MatrixLayout::RowMajor), block_size)
1134 }
1135 AccessPattern::Random => MatrixLayout::RowMajor,
1136 AccessPattern::Adaptive => {
1137 if matrix.rows > matrix.cols {
1138 MatrixLayout::ColMajor
1139 } else {
1140 MatrixLayout::RowMajor
1141 }
1142 }
1143 };
1144 self.transform_matrix(matrix, target)
1145 }
1146}
1147
1148fn padded_stride(cols: usize) -> usize {
1151 ((cols + SIMD_WIDTH - 1) / SIMD_WIDTH) * SIMD_WIDTH
1152}
1153
1154fn read_element(matrix: &Matrix, i: usize, j: usize) -> Result<f64, LinearAlgebraError> {
1158 let rows = matrix.rows;
1159 let cols = matrix.cols;
1160 if i >= rows || j >= cols {
1161 return Err(LinearAlgebraError::OptimizationError(format!(
1162 "element index ({}, {}) out of bounds for matrix of shape {}x{}",
1163 i, j, rows, cols
1164 )));
1165 }
1166 let idx = match matrix.storage_format {
1167 StorageFormat::RowMajor => i * cols + j,
1168 StorageFormat::ColumnMajor => j * rows + i,
1169 StorageFormat::Packed => {
1170 let stride = padded_stride(cols);
1171 i * stride + j
1172 }
1173 StorageFormat::Blocked => {
1174 return Err(LinearAlgebraError::OptimizationError(
1175 "cannot read from Blocked source: block size is not stored in Matrix metadata"
1176 .to_string(),
1177 ));
1178 }
1179 StorageFormat::CompressedSparseRow | StorageFormat::CompressedSparseColumn => {
1180 return Err(LinearAlgebraError::OptimizationError(
1181 "sparse source layouts are not supported by the layout transformer".to_string(),
1182 ));
1183 }
1184 };
1185 if idx >= matrix.data.len() {
1186 return Err(LinearAlgebraError::OptimizationError(format!(
1187 "linear index {} out of bounds for data buffer of length {} (layout {:?})",
1188 idx,
1189 matrix.data.len(),
1190 matrix.storage_format
1191 )));
1192 }
1193 Ok(matrix.data[idx])
1194}
1195
1196fn validate_source_buffer(matrix: &Matrix) -> Result<(), LinearAlgebraError> {
1199 let expected = match matrix.storage_format {
1200 StorageFormat::RowMajor | StorageFormat::ColumnMajor | StorageFormat::Blocked => {
1201 matrix.rows * matrix.cols
1202 }
1203 StorageFormat::Packed => matrix.rows * padded_stride(matrix.cols),
1204 StorageFormat::CompressedSparseRow | StorageFormat::CompressedSparseColumn => {
1205 return Ok(());
1208 }
1209 };
1210 if matrix.data.len() != expected {
1211 return Err(LinearAlgebraError::OptimizationError(format!(
1212 "source data length {} does not match expected {} for {:?} layout ({}x{})",
1213 matrix.data.len(),
1214 expected,
1215 matrix.storage_format,
1216 matrix.rows,
1217 matrix.cols
1218 )));
1219 }
1220 Ok(())
1221}
1222
1223#[derive(Debug, Clone)]
1224pub struct MatrixAnalysis {
1225 pub matrix_id: String,
1226 pub sparsity: f64,
1227 pub structure: MatrixPattern,
1228 pub detected_patterns: Vec<MatrixPattern>,
1230 pub access_pattern: AccessPattern,
1231 pub optimization_hints: Vec<String>,
1232 pub recommended_algorithms: Vec<String>,
1234}
1235
1236pub type MatrixAnalysisResult = MatrixAnalysis;
1238
1239#[cfg(test)]
1240mod tests {
1241 use super::*;
1242
1243 fn make_matrix(id: &str, rows: usize, cols: usize, data: Vec<f64>) -> Matrix {
1244 let metadata = MatrixMetadata {
1245 matrix_id: id.to_string(),
1246 rows,
1247 cols,
1248 data_type: DataType::Float64,
1249 storage_format: StorageFormat::RowMajor,
1250 compression: CompressionType::None,
1251 created_at: 0,
1252 last_accessed: 0,
1253 access_count: 0,
1254 };
1255 Matrix {
1256 matrix_id: id.to_string(),
1257 rows,
1258 cols,
1259 data_type: DataType::Float64,
1260 data,
1261 storage_format: StorageFormat::RowMajor,
1262 metadata,
1263 }
1264 }
1265
1266 fn make_analyzer() -> MatrixAnalyzer {
1267 let mut analyzer = MatrixAnalyzer::new();
1268 analyzer.initialize().unwrap();
1269 analyzer
1270 }
1271
1272 #[test]
1273 fn test_detect_diagonal() {
1274 let analyzer = make_analyzer();
1275 let m = make_matrix("d", 3, 3, vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0]);
1277 let patterns = analyzer.detect_structure(&m);
1278 assert!(patterns.contains(&MatrixPattern::Diagonal));
1279 }
1280
1281 #[test]
1282 fn test_detect_upper_triangular() {
1283 let analyzer = make_analyzer();
1284 let m = make_matrix("u", 3, 3, vec![1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0]);
1285 let patterns = analyzer.detect_structure(&m);
1286 assert!(patterns.contains(&MatrixPattern::Triangular));
1287 }
1288
1289 #[test]
1290 fn test_detect_lower_triangular() {
1291 let analyzer = make_analyzer();
1292 let m = make_matrix("l", 3, 3, vec![1.0, 0.0, 0.0, 2.0, 3.0, 0.0, 4.0, 5.0, 6.0]);
1293 let patterns = analyzer.detect_structure(&m);
1294 assert!(patterns.contains(&MatrixPattern::Triangular));
1295 }
1296
1297 #[test]
1298 fn test_detect_symmetric() {
1299 let analyzer = make_analyzer();
1300 let m = make_matrix("s", 3, 3, vec![1.0, 2.0, 3.0, 2.0, 4.0, 5.0, 3.0, 5.0, 6.0]);
1301 let patterns = analyzer.detect_structure(&m);
1302 assert!(patterns.contains(&MatrixPattern::Symmetric));
1303 }
1304
1305 #[test]
1306 fn test_detect_not_symmetric() {
1307 let analyzer = make_analyzer();
1308 let m = make_matrix("ns", 2, 2, vec![1.0, 2.0, 3.0, 4.0]);
1309 let patterns = analyzer.detect_structure(&m);
1310 assert!(!patterns.contains(&MatrixPattern::Symmetric));
1311 }
1312
1313 #[test]
1314 fn test_detect_positive_definite() {
1315 let analyzer = make_analyzer();
1316 let m = make_matrix("pd", 2, 2, vec![2.0, 1.0, 1.0, 2.0]);
1318 let patterns = analyzer.detect_structure(&m);
1319 assert!(patterns.contains(&MatrixPattern::PositiveDefinite));
1320 }
1321
1322 #[test]
1323 fn test_detect_not_positive_definite() {
1324 let analyzer = make_analyzer();
1325 let m = make_matrix("npd", 2, 2, vec![1.0, 2.0, 2.0, 1.0]);
1327 let patterns = analyzer.detect_structure(&m);
1328 assert!(!patterns.contains(&MatrixPattern::PositiveDefinite));
1329 }
1330
1331 #[test]
1332 fn test_detect_sparse() {
1333 let analyzer = make_analyzer();
1334 let m = make_matrix(
1336 "sp",
1337 4,
1338 4,
1339 vec![
1340 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0,
1341 ],
1342 );
1343 let patterns = analyzer.detect_structure(&m);
1344 assert!(patterns.contains(&MatrixPattern::Sparse));
1345 }
1346
1347 #[test]
1348 fn test_detect_dense() {
1349 let analyzer = make_analyzer();
1350 let m = make_matrix("d", 2, 2, vec![1.0, 2.0, 3.0, 4.0]);
1351 let patterns = analyzer.detect_structure(&m);
1352 assert!(patterns.contains(&MatrixPattern::Dense));
1353 }
1354
1355 #[test]
1356 fn test_detect_banded() {
1357 let analyzer = make_analyzer();
1358 let m = make_matrix(
1360 "b",
1361 5,
1362 5,
1363 vec![
1364 1.0, 2.0, 0.0, 0.0, 0.0, 3.0, 4.0, 5.0, 0.0, 0.0, 0.0, 6.0, 7.0, 8.0, 0.0, 0.0,
1365 0.0, 9.0, 10.0, 11.0, 0.0, 0.0, 0.0, 12.0, 13.0,
1366 ],
1367 );
1368 let patterns = analyzer.detect_structure(&m);
1369 assert!(patterns.contains(&MatrixPattern::Banded));
1370 }
1371
1372 #[test]
1373 fn test_detect_toeplitz() {
1374 let analyzer = make_analyzer();
1375 let m = make_matrix("t", 3, 3, vec![1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 5.0, 4.0, 1.0]);
1378 let patterns = analyzer.detect_structure(&m);
1379 assert!(patterns.contains(&MatrixPattern::Toeplitz));
1380 }
1381
1382 #[test]
1383 fn test_detect_orthogonal() {
1384 let analyzer = make_analyzer();
1385 let m = make_matrix("o", 2, 2, vec![0.0, -1.0, 1.0, 0.0]);
1388 let patterns = analyzer.detect_structure(&m);
1389 assert!(patterns.contains(&MatrixPattern::Orthogonal));
1390 }
1391
1392 #[test]
1393 fn test_detect_circulant() {
1394 let analyzer = make_analyzer();
1395 let m = make_matrix("c", 3, 3, vec![1.0, 2.0, 3.0, 3.0, 1.0, 2.0, 2.0, 3.0, 1.0]);
1398 let patterns = analyzer.detect_structure(&m);
1399 assert!(patterns.contains(&MatrixPattern::Circulant));
1400 }
1401
1402 #[test]
1403 fn test_detect_hankel() {
1404 let analyzer = make_analyzer();
1405 let m = make_matrix("h", 3, 3, vec![1.0, 2.0, 3.0, 2.0, 3.0, 4.0, 3.0, 4.0, 5.0]);
1408 let patterns = analyzer.detect_structure(&m);
1409 assert!(patterns.contains(&MatrixPattern::Hankel));
1410 }
1411
1412 #[test]
1413 fn test_detect_block_diagonal() {
1414 let analyzer = make_analyzer();
1415 let m = make_matrix(
1417 "bd",
1418 4,
1419 4,
1420 vec![
1421 1.0, 2.0, 0.0, 0.0, 3.0, 4.0, 0.0, 0.0, 0.0, 0.0, 5.0, 6.0, 0.0, 0.0, 7.0, 8.0,
1422 ],
1423 );
1424 let patterns = analyzer.detect_structure(&m);
1425 assert!(patterns.contains(&MatrixPattern::BlockDiagonal));
1426 }
1427
1428 #[test]
1429 fn test_pattern_library_initialize() {
1430 let mut lib = PatternLibrary::new();
1431 lib.initialize().unwrap();
1432
1433 assert_eq!(lib.patterns.len(), 12);
1435 assert_eq!(lib.optimization_hints.len(), 12);
1436 }
1437
1438 #[test]
1439 fn test_get_optimization_hint() {
1440 let mut lib = PatternLibrary::new();
1441 lib.initialize().unwrap();
1442
1443 let hint = lib.get_optimization_hint(&MatrixPattern::Diagonal);
1444 assert!(hint.is_some());
1445 let h = hint.unwrap();
1446 assert_eq!(h.preferred_algorithm, "diagonal_scale");
1447 assert!(h.estimated_speedup > 0.0);
1448
1449 let hint2 = lib.get_optimization_hint(&MatrixPattern::Sparse);
1450 assert!(hint2.is_some());
1451 assert_eq!(hint2.unwrap().preferred_algorithm, "sparse_gemm");
1452 }
1453
1454 #[test]
1455 fn test_analyze_matrix() {
1456 let mut analyzer = make_analyzer();
1457 let m = make_matrix("s", 2, 2, vec![2.0, 1.0, 1.0, 2.0]);
1458 let result = analyzer.analyze_matrix(&m).unwrap();
1459
1460 assert_eq!(result.matrix_id, "s");
1461 assert!(result.detected_patterns.contains(&MatrixPattern::Symmetric));
1462 assert!(result
1463 .detected_patterns
1464 .contains(&MatrixPattern::PositiveDefinite));
1465 assert!(!result.recommended_algorithms.is_empty());
1466 }
1467
1468 #[test]
1469 fn test_analyze_matrix_sparsity() {
1470 let mut analyzer = make_analyzer();
1471 let m = make_matrix(
1473 "sp",
1474 3,
1475 3,
1476 vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0],
1477 );
1478 let result = analyzer.analyze_matrix(&m).unwrap();
1479 assert!((result.sparsity - 6.0 / 9.0).abs() < 1e-10); }
1481
1482 fn make_transformer() -> MatrixTransformer {
1485 let mut t = MatrixTransformer::new();
1486 t.initialize().unwrap();
1487 t
1488 }
1489
1490 fn make_col_matrix(id: &str, rows: usize, cols: usize, row_major_data: Vec<f64>) -> Matrix {
1494 let mut col_major = Vec::with_capacity(rows * cols);
1496 for j in 0..cols {
1497 for i in 0..rows {
1498 col_major.push(row_major_data[i * cols + j]);
1499 }
1500 }
1501 let metadata = MatrixMetadata {
1502 matrix_id: id.to_string(),
1503 rows,
1504 cols,
1505 data_type: DataType::Float64,
1506 storage_format: StorageFormat::ColumnMajor,
1507 compression: CompressionType::None,
1508 created_at: 0,
1509 last_accessed: 0,
1510 access_count: 0,
1511 };
1512 Matrix {
1513 matrix_id: id.to_string(),
1514 rows,
1515 cols,
1516 data_type: DataType::Float64,
1517 data: col_major,
1518 storage_format: StorageFormat::ColumnMajor,
1519 metadata,
1520 }
1521 }
1522
1523 fn read_blocked(m: &Matrix, block_size: usize, i: usize, j: usize) -> f64 {
1527 let rows = m.rows;
1528 let cols = m.cols;
1529 let block_rows = (rows + block_size - 1) / block_size;
1530 let block_cols = (cols + block_size - 1) / block_size;
1531 let bi = i / block_size;
1532 let bj = j / block_size;
1533 let li = i % block_size; let lj = j % block_size; let mut offset = 0usize;
1537 'outer: for bbi in 0..block_rows {
1538 for bbj in 0..block_cols {
1539 if bbi == bi && bbj == bj {
1540 break 'outer;
1541 }
1542 let i_end = rows.min((bbi + 1) * block_size);
1543 let j_end = cols.min((bbj + 1) * block_size);
1544 offset += (i_end - bbi * block_size) * (j_end - bbj * block_size);
1545 }
1546 }
1547 let i_start = bi * block_size;
1549 let j_start = bj * block_size;
1550 let _local_rows = rows.min((bi + 1) * block_size) - i_start;
1551 let local_cols = cols.min((bj + 1) * block_size) - j_start;
1552 offset += li * local_cols + lj;
1554 m.data[offset]
1555 }
1556
1557 #[test]
1558 fn test_row_to_col_major() {
1559 let transformer = make_transformer();
1560 let m = make_matrix("rm", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1564 assert_eq!(m.storage_format, StorageFormat::RowMajor);
1565
1566 let result = transformer
1567 .transform_matrix(&m, MatrixLayout::ColMajor)
1568 .unwrap();
1569
1570 assert_eq!(result.storage_format, StorageFormat::ColumnMajor);
1571 assert_eq!(result.metadata.storage_format, StorageFormat::ColumnMajor);
1572 assert_eq!(result.rows, 2);
1573 assert_eq!(result.cols, 3);
1574 assert_eq!(result.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1576 for i in 0..2 {
1578 for j in 0..3 {
1579 let expected = m.data[i * 3 + j];
1580 let got = result.data[j * 2 + i];
1581 assert_eq!(got, expected, "element ({},{}) mismatch", i, j);
1582 }
1583 }
1584 }
1585
1586 #[test]
1587 fn test_col_to_row_major() {
1588 let transformer = make_transformer();
1589 let m = make_col_matrix("cm", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1591 assert_eq!(m.storage_format, StorageFormat::ColumnMajor);
1592 assert_eq!(m.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1593
1594 let result = transformer
1595 .transform_matrix(&m, MatrixLayout::RowMajor)
1596 .unwrap();
1597
1598 assert_eq!(result.storage_format, StorageFormat::RowMajor);
1599 assert_eq!(result.rows, 2);
1600 assert_eq!(result.cols, 3);
1601 assert_eq!(result.data, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1603 for i in 0..2 {
1605 for j in 0..3 {
1606 let expected = m.data[j * 2 + i]; let got = result.data[i * 3 + j]; assert_eq!(got, expected, "element ({},{}) mismatch", i, j);
1609 }
1610 }
1611 }
1612
1613 #[test]
1614 fn test_blocked_layout() {
1615 let transformer = make_transformer();
1616 let m = make_matrix(
1622 "blk",
1623 4,
1624 4,
1625 vec![
1626 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0,
1627 16.0,
1628 ],
1629 );
1630
1631 let result = transformer
1632 .transform_matrix(
1633 &m,
1634 MatrixLayout::Blocked(Box::new(MatrixLayout::RowMajor), 2),
1635 )
1636 .unwrap();
1637
1638 assert_eq!(result.storage_format, StorageFormat::Blocked);
1639 assert_eq!(result.rows, 4);
1640 assert_eq!(result.cols, 4);
1641 assert_eq!(result.data.len(), 16);
1642 assert_eq!(
1648 result.data,
1649 vec![
1650 1.0, 2.0, 5.0, 6.0, 3.0, 4.0, 7.0, 8.0, 9.0, 10.0, 13.0, 14.0, 11.0, 12.0, 15.0,
1651 16.0,
1652 ]
1653 );
1654 for i in 0..4 {
1656 for j in 0..4 {
1657 let expected = m.data[i * 4 + j];
1658 let got = read_blocked(&result, 2, i, j);
1659 assert_eq!(got, expected, "blocked element ({},{}) mismatch", i, j);
1660 }
1661 }
1662 }
1663
1664 #[test]
1665 fn test_optimize_layout_row_access() {
1666 let transformer = make_transformer();
1667 let m = make_matrix("r", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1668 let result = transformer
1670 .optimize_layout(&m, &AccessPattern::Sequential)
1671 .unwrap();
1672 assert_eq!(result.storage_format, StorageFormat::RowMajor);
1673 assert_eq!(result.data, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1675 }
1676
1677 #[test]
1678 fn test_optimize_layout_col_access() {
1679 let transformer = make_transformer();
1680 let m = make_matrix("c", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1681 let result = transformer
1683 .optimize_layout(&m, &AccessPattern::Strided)
1684 .unwrap();
1685 assert_eq!(result.storage_format, StorageFormat::ColumnMajor);
1686 assert_eq!(result.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1688 }
1689
1690 #[test]
1693 fn test_pattern_recognition_accumulates_patterns() {
1694 let mut analyzer = make_analyzer();
1695 assert!(analyzer.pattern_recognition.recognized_patterns.is_empty());
1696
1697 let m_diag = make_matrix("d", 3, 3, vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0]);
1699 analyzer.analyze_matrix(&m_diag).unwrap();
1700 assert!(analyzer
1701 .pattern_recognition
1702 .recognized_patterns
1703 .contains(&MatrixPattern::Diagonal));
1704
1705 let m_toep = make_matrix(
1707 "t",
1708 3,
1709 3,
1710 vec![1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 5.0, 4.0, 1.0],
1711 );
1712 analyzer.analyze_matrix(&m_toep).unwrap();
1713 assert!(analyzer
1714 .pattern_recognition
1715 .recognized_patterns
1716 .contains(&MatrixPattern::Toeplitz));
1717 }
1718
1719 #[test]
1720 fn test_optimizer_strategy_registry_and_resolution() {
1721 let mut opt = MatrixOptimizer::new();
1722 assert!(opt.is_strategy_enabled(&OptimizationStrategy::AlgorithmSelection));
1723 assert!(opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1724
1725 opt.unregister_strategy(&OptimizationStrategy::Parallelization);
1727 assert!(!opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1728
1729 let fallbacks = [
1731 OptimizationStrategy::CacheOptimization,
1732 OptimizationStrategy::Vectorization,
1733 ];
1734 let chosen = opt
1735 .resolve_strategy(OptimizationStrategy::Parallelization, &fallbacks)
1736 .unwrap();
1737 assert_eq!(chosen, OptimizationStrategy::CacheOptimization);
1738
1739 opt.register_strategy(OptimizationStrategy::Parallelization);
1741 assert!(opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1742 let chosen2 = opt
1743 .resolve_strategy(OptimizationStrategy::Parallelization, &fallbacks)
1744 .unwrap();
1745 assert_eq!(chosen2, OptimizationStrategy::Parallelization);
1746 }
1747
1748 #[test]
1749 fn test_optimize_multiplication_consults_hints_and_strategies() {
1750 let mut engine = OptimizationEngine::new();
1751 engine.initialize().unwrap();
1752
1753 let m_diag = make_matrix("d", 3, 3, vec![2.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 4.0]);
1755 let m_dense = make_matrix("dn", 3, 3, vec![1.0; 9]);
1756
1757 let opt_mult = engine.optimize_multiplication(&m_diag, &m_dense).unwrap();
1758 assert_eq!(
1759 opt_mult.optimization_strategy,
1760 OptimizationStrategy::AlgorithmSelection
1761 );
1762 assert!(opt_mult.expected_performance_gain >= 10.0);
1763 assert_eq!(engine.optimizer.optimization_history.len(), 1);
1764
1765 engine
1767 .optimizer
1768 .unregister_strategy(&OptimizationStrategy::AlgorithmSelection);
1769 let opt_mult_fallback = engine.optimize_multiplication(&m_diag, &m_dense).unwrap();
1770 assert_ne!(
1771 opt_mult_fallback.optimization_strategy,
1772 OptimizationStrategy::AlgorithmSelection
1773 );
1774 assert!(engine
1775 .optimizer
1776 .is_strategy_enabled(&opt_mult_fallback.optimization_strategy));
1777 }
1778}